Bombing (Easy Version)

Let $pos[x]$ be the final position of value $x$.

For a split $k$, being a riffle shuffle of $[1,2,\dots,n]$ means:

$$pos[1] < pos[2] < \cdots < pos[k]$$

and

$$pos[k+1] < pos[k+2] < \cdots < pos[n].$$

So in the value-position sequence

$$pos[1], pos[2], \dots, pos[n],$$

all adjacent pairs must increase except maybe the pair $(k,k+1)$.

That gives the main characterization:

A permutation is valid iff $pos[1..n]$ has at most one descent.

If there is no descent, then $pos[1]<pos[2]<\cdots<pos[n]$, so the permutation is exactly sorted: $[1,2,\dots,n]$.

If there is exactly one descent after value $k$, then split $k$ is the only possible split. No double-counting nonsense.

Now count, for each split $k$, all completions that work for that split. Then the only duplicate across different $k$ is the sorted permutation, because sorted works for every split. Everything else has one unique descent boundary.

So the answer is:

$$[\text{sorted matches input}] + \sum_{k=1}^{n-1}(ways(k)-[\text{sorted matches input}]).$$

Here $ways(k)$ means: number of completions that are valid for split $k$.

Counting one split

Fix $k$.

Every split-$k$ riffle shuffle can be represented by a binary string of length $n$:

• L: this position gets the next value from $1,2,\dots,k$;
• R: this position gets the next value from $k+1,k+2,\dots,n$.

For example, if $k=3$ and the binary string is LRRLLR, the values are filled as:

$$1,4,5,2,3,6.$$

Once the binary string is chosen, the actual permutation is forced.

Now look at a fixed input cell $p_i=a$.

Suppose we scan positions left to right. After processing position $i$, let:

• $L$ = number of L positions used so far;
• $R$ = number of R positions used so far.

Of course $L+R=i$.

If $a\le k$, then $a$ belongs to the left block. Therefore position $i$ must be an L, and after taking that step we need:

$$L=a,\quad R=i-a.$$

If $a>k$, then $a$ belongs to the right block. It is the $(a-k)$-th right value, so position $i$ must be an R, and after taking that step:

$$R=a-k,\quad L=i-(a-k).$$

So every fixed cell becomes a forced checkpoint in the binary string, plus a forced final step type for that checkpoint.

Using binomial coefficients between checkpoints

Process fixed cells in increasing position order.

Assume the previous checkpoint was after position lastPos, with counts (lastL, lastR). Now the next fixed cell is at position $i$, and it requires counts (L, R) after position $i`.

Let:

$$len=i-lastPos,$$ $$dL=L-lastL,\quad dR=R-lastR.$$

We need exactly $dL$ left steps and $dR$ right steps in this segment.

But the last step of the segment, position $i$, is forced:

• if position $i$ must be L, then among the previous $len-1$ positions we choose $dL-1$ left steps:

$$\binom{len-1}{dL-1};$$

• if position $i$ must be R, then among the previous $len-1$ positions we choose $dL$ left steps:

$$\binom{len-1}{dL}.$$

If counts ever go backward, exceed $k$ or $n-k$, or the forced step is impossible, then this split contributes $0$.

After the last fixed cell, the remaining suffix has no forced endpoint. If we still need $dL$ left steps in a suffix of length $len$, it contributes:

$$\binom{len}{dL}.$$

That gives $ways(k)$ in $O(\#fixed)$ time.

We do this for all $k=1..n-1$, so the total complexity is $O(n^2)$ per test file overall because the sum of $n$ is at most $3000$. Completely fine.

Why subtract sorted?

For every split $k$, the sorted permutation corresponds to binary string:

$$LL\cdots LRR\cdots R.$$

So if the sorted permutation matches the fixed input, it appears inside every $ways(k)$. But it is one permutation, not $n-1$ permutations wearing fake mustaches.

All non-sorted valid permutations have exactly one descent in $pos[1..n]$, so they are counted for exactly one split.

That is the whole trick.