Appending Permutations (Easy Version)

The annoying part

If we just count ways to split the array into appended blocks, we overcount. The task asks for distinct arrays, not distinct operation histories.

Example:

$[1,2,1]$

can be built as

$[1,2]+[1]$

or as

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

Same array, two decompositions. So the naive composition DP faceplants immediately.

Identity blocks and the duplicate pattern

Call a block identity if it is exactly

$[1,2,...,s]$.

Now look at this equality for $x>y$:

$[1,2,...,y] + [y+1,y+2,...,x,1,2,...,y]$

is the same array as

$[1,2,...,x] + [1,2,...,y]$.

Both sides are just

$[1,2,...,x,1,2,...,y]$.

This is exactly the duplicate mechanism. The left side is:

• identity block of length $y$,
• then a shifted block whose first value is $y+1$.

The right side is:

• identity block of length $x$,
• then identity block of length $y$.

We need keep one representation and throw away the other. The clean rule is:

If the previous block was identity of length $y$, then do not append a shifted block starting with $y+1$.

That gives a canonical decomposition.

Why is this enough? Suppose two valid decompositions create the same array. Compare them from the left and find the first place where their block boundaries differ. The shorter first block must be a full cyclic block sitting inside the prefix of the longer cyclic block. Since the longer block has length bigger than the shorter one, the only way this prefix uses exactly the values of the shorter block is that both start as $[1,2,...]$. So the shorter decomposition has an identity block of length $y$, and the next block must continue with value $y+1$. That is precisely the banned pattern. So two canonical decompositions cannot represent the same array.

Also, every array has at least one canonical decomposition: start with any decomposition and whenever the banned pattern appears, replace it with the other side above. This keeps the final array identical and removes one shifted block, so the process terminates. No magic, just local cleanup.

Checking whether a block is allowed

Suppose we append a block of length $len$ starting at position $pos+1$, and its first value is $first$.

For offset $k=0,1,...,len-1$, the forced value is

$((first-1+k) \bmod len)+1$.

So this block is valid iff none of those forced values violates a restriction $a_i \ne x$.

Since $n \le 100$, we can precompute this directly for every start position, length, and first value. Tiny constraints, caveman loops accepted.

DP state

Let

$dp[pos][last]$

be the number of canonical ways to build the first $pos$ positions, where:

• $last=0$ means the last block is not identity, or the prefix is empty,
• $last>0$ means the last block is identity of length $last$.

Initialize:

$dp[0][0]=1$.

Now from a state $(pos,last)$, try appending every block:

• length $len$,
• first value $first$.

The block covers positions $pos+1$ through $pos+len$.

We skip it if:

1. it violates some restriction, or
2. $last>0$ and $first=last+1$.

The second condition is exactly the canonical ban.

After appending:

• if $first=1$, the new block is identity, so the next state has last = len,
• otherwise it is shifted, so the next state has last = 0.

The answer is

$\sum_{last=0}^{n} dp[n][last]$.

Complexity

Precomputing valid blocks costs $O(n^4)$ in the straightforward version.

The DP also costs $O(n^4)$: there are $O(n^2)$ states and $O(n^2)$ possible next blocks.

For $n \le 100$, this is completely fine.