Bombing (Hard Version)

Core View

Fix a split $s$: the left subsequence is $1,2,\ldots,s$, and the right subsequence is $s+1,s+2,\ldots,n$. If we color every position by whether it comes from the left or right subsequence, then the values are forced: left-colored positions receive the next left value, right-colored positions receive the next right value.

So the problem is really counting valid two-colorings of the unknown positions. The annoying part is that we must count completed permutations, not split choices. A non-sorted valid permutation has a unique split. The sorted permutation works for every split, so it needs special handling.

The implementation uses 0-indexed values. So a split $s$ means:

• left values are $0,1,\ldots,s-1$,
• right values are $s,s+1,\ldots,n-1$.

Valid real splits are $1 \le s \le n-1$.

Forcing The Side Of Known Values

Suppose position $i$ contains known value $x$.

If $x$ is on the left side, then by the time we reach position $i$, the left values $0,1,\ldots,x$ have appeared. That is $x+1$ left values inside $i+1$ positions, so $x \le i$.

If $x$ is on the right side, then all positions up to $i$ contain at most all $s$ left values plus some prefix of the right values. This gives $x \ge i$.

Therefore:

• $x<i$ forces the value to be left,
• $x>i$ forces the value to be right,
• $x=i$ is the only ambiguous case.

But in a non-sorted valid permutation, fixed points $p_i=i$ are not scattered randomly. They form a sorted prefix and a sorted suffix. Once the permutation actually deviates from sorted order, the middle cannot contain another fixed point. So if at least one known value has $x \ne i$, then while scanning left to right:

• known fixed points before the first non-fixed known value are left,
• known fixed points after that are right.

That gives the side of every known value.

Case 1: Sorted Completion Is Still Possible

This means every known value is either $-1$ or exactly its own index.

The fully sorted completion always contributes $1$.

Now consider one maximal run of $m$ unknown positions between fixed known positions or array borders. The values that can go there are exactly the same consecutive interval, so the run behaves like a smaller all-unknown problem of length $m$.

For length $m$, summing over split choices gives

$\sum_{s=1}^{m-1} \binom{m}{s}=2^m-2.$

Every non-sorted riffle shuffle is counted once, while the sorted order is counted $m-1$ times. So the number of distinct valid permutations is $2^m-m$, and the number of non-sorted ones is $2^m-m-1$.

Only one run can contain the unique non-sorted part; otherwise the inverse permutation would have multiple descents. So the answer in this case is

$1 + \sum_{\text{unknown runs}} (2^m-m-1).$

Tiny formula, big win. Very suspicious-looking, but it is exactly the sorted-overcount tax.

Case 2: Sorted Completion Is Impossible

Now every valid completion is non-sorted, hence has a unique split $s$. We can safely sum over $s$.

We already know the side of each known value. Process gaps of unknown positions between consecutive known positions. Also add a fake left-side sentinel before the array with value $-1$; this makes the first known value behave like an ordinary gap.

For a gap of length $m$ between known endpoints, the number of ways to choose which unknown positions are right-side is always a binomial coefficient. The formula depends on the endpoint sides.

Let the previous known endpoint be at position $u$ with value $A$, and the next known endpoint be at position $v$ with value $B$. The gap length is $m=v-u-1$.

For same-side gaps:

• left $\to$ left: we must place exactly $B-A-1$ left values inside the gap;
• right $\to$ right: we must place exactly $B-A-1$ right values inside the gap.

Either way, the contribution is simply

$\binom{m}{B-A-1},$

independent of $s$. We multiply these into a global coefficient.

For crossing gaps, the contribution depends on $s$.

For left $\to$ right, the number of right positions needed inside the gap is

$B-s-(u-A).$

So this gap contributes

$\binom{m}{B-s-(u-A)}.$

It is nonzero only when

$B-(u-A)-m \le s \le B-(u-A).$

For right $\to$ left, the number of right positions needed inside the gap is

$s+v-B-A-1,$

so the contribution is

$\binom{m}{s+v-B-A-1},$

nonzero only when

$A+B+1-v \le s \le A+B+1-v+m.$

Each crossing gap of length $m$ allows only $m+1$ split values. Intersect all these ranges with $1 \le s \le n-1$. Let the final interval be $[L,R]$.

Then we keep score[s] for every $s\in[L,R]`, initialized to$1. For every crossing gap, multiply the proper binomial into score[s]. For every same-side gap, multiply its binomial into a global coef`.

Finally, handle the suffix after the last known value:

• if the last known value is left with value $A$, then we still need $s-A-1$ left positions in the suffix;
• if it is right with value $A$, then we still need $n-1-A$ right positions in the suffix.

Add all score[s], multiply by coef, and that is the answer.

Why This Is Linear

Let the final candidate interval have size $X$. Every crossing gap used to create that interval has length at least $X-1$, because a crossing gap of length $m$ allows only $m+1$ split values. These crossing gaps are disjoint, so the total work over all crossing gaps is $O(n)$. Same-side gaps are processed once. Precomputed factorials give every binomial in $O(1)$.

Total complexity: $O(n)$ per test case, with $O(n)$ memory. Across all tests, $O(\sum n)$.