Appending Permutations (Hard Version)

The annoying part is not restrictions. The annoying part is that the same array can have multiple decompositions.

For example:

$[1,2,1] = [1] + [2,1] = [1,2] + [1]$.

If we count operation sequences, we overcount. We need one canonical decomposition per final array.

Canonical Rule

Call $I_L=[1,2,\ldots,L]$. For $x>y$,

$I_y + [y+1,y+2,\ldots,x,1,2,\ldots,y] = I_x + I_y.$

So whenever an identity block of length $y$ is followed by a block whose first value is $y+1$, that boundary is fake. We ban exactly that case.

This is the whole trick. Any non-canonical boundary can be rewritten using the identity above, and repeated rewrites terminate. After the ban, the first block is forced by the array:

• if the first value is $1$, the first block is an identity block, and stopping at length $L$ is illegal exactly when the remaining suffix starts with $L+1$;
• if the first value is $x>1$, the block start is fixed, and the position where it wraps to $1$ is fixed by the array.

Then recurse on the suffix. So counting canonical decompositions counts distinct arrays, not parse nonsense.

Handling Restrictions With chain

Let chain[i][x] be the maximum $k$ such that positions $i,i+1,\ldots,i+k-1$ may be filled with $x,x+1,\ldots,x+k-1$.

If value $x$ is forbidden at position $i$, then chain[i][x]=0; otherwise

$chain[i][x]=1+chain[i+1][x+1].$

Out-of-range positions or values contribute $0$. This is $O(n^2+m)$.

DP States

Use 1-indexed positions in the explanation.

Let $dp[i][x]$ be the number of valid canonical arrays on suffix $i,\ldots,n$ whose first value is exactly $x$.

Let

$tot[i]=\sum_x dp[i][x],$

with $tot[n+1]=1$ for the empty suffix.

The answer is $tot[1]$.

Transition When The Suffix Starts With $1$

If $a_i=1$, the first block must be an identity block of some length $L$.

It is allowed only if chain[i][1] >= L. After taking it, the rest contributes $tot[i+L]$.

But if the next suffix starts with $L+1$, this violates our canonical ban: identity length $L$ followed by a block starting with $L+1$. So subtract those.

$$dp[i][1]=\sum_{L=1}^{chain[i][1]} \left(tot[i+L]-dp[i+L][L+1]\right).$$

Treat $dp[n+1][*]=0$.

Transition When The Suffix Starts With $x>1$

The first block begins

$x,x+1,x+2,\ldots$

then at some position $p$ it wraps and writes

$1,2,\ldots,x-1.$

The increasing part from $i$ to $p-1$ has length between $1$ and chain[i][x], so

$i+1 \le p \le i+chain[i][x].$

For a fixed $p$, the wrapped tail is legal iff chain[p][1] >= x-1, and then the remaining suffix contributes $tot[p+x-1]$.

Naively this is too slow if we sum over all $p$ each time, so precompute

$$suff[i][x]=\sum_{p=i}^{n} [chain[p][1]\ge x-1]\cdot tot[p+x-1].$$

Then

$$dp[i][x]=suff[i+1][x]-suff[i+1+chain[i][x]][x].$$

That is just the range of valid wrap positions.

After computing all $dp[i][x]$, compute $tot[i]$, then update

$$suff[i][x]=suff[i+1][x]+[chain[i][1]\ge x-1]\cdot tot[i+x-1].$$

Everything is processed from right to left, so all future suffix values are already known.

Complexity

There are $O(n^2)$ states and each transition is $O(1)$ except the identity-start case. Across all $i$, those identity sums are also $O(n^2)$ because the total possible lengths is triangular.

Memory is $O(n^2)$, which is fine for $n\le 5000$ under the big memory limit.