Editorial: Prime Gaming (Hard Version)

The hard version keeps the same game core as E1; only aggregation over large $m$ matters. So build the solution incrementally from a fixed configuration.

1) Step A: fixed configuration

Fix one array of values. The sequence of legal moves depends only on good indices and reindexing, not on numeric magnitudes.

For a threshold $a$, replace each value by:

$0$ if value $< a$
$1$ if value $\ge a$

Then the objective becomes binary:

Alice wants final bit $1$
Bob wants final bit $0$

So for each threshold, we only need to answer whether Alice can force a final $1$.

2) Step B: minimax DP on masks

Represent current length-$l$ binary sequence as a bitmask. Transition by deleting one legal good index $i$.

Define win(mask, l):

$1$: Alice can force final bit $1$ from this state
$0$: Bob can prevent that

Base:

$l = 1$: result is the remaining bit itself.

Transition:

Alice turn: OR over all legal deletions
Bob turn: AND over all legal deletions

In implementation, this is often flattened into one dp array indexed by a sentinel-prefixed mask (same style as the provided model solution).

3) Step C: from one threshold to all arrays

After DP, every full-length mask is winning or losing for threshold $a$. Let $K_c$ be the number of winning masks with exactly $c$ zeros (positions with value $< a$).

For such a mask:

each zero has $(a - 1)$ choices,
each one has $(m - a + 1)$ choices.

Contribution count:

$$ (a - 1)^c (m - a + 1)^{n-c}. $$

Therefore

$$ F(a) = \#\{\text{arrays with final } x \ge a\} = \sum_{c=0}^{n} K_c (a - 1)^c (m - a + 1)^{n-c}. $$

4) Step D: incremental difficulty to full answer

For a single fixed configuration, you only solve one game. For one threshold $a$, you solve game outcomes on all binary masks. Then you aggregate counts for that $a$. Finally, sum over all thresholds:

$$ \sum_{\text{arrays}} x = \sum_{a=1}^{m} F(a). $$

This identity is a standard “sum of indicators” trick: an array with final value $x$ contributes to every threshold $a \le x$.

5) Practical implementation notes

Precompute popcount for masks up to $2^{20}$.
Build DP by increasing current length.
Precompute/iteratively update powers of $(a - 1)$ and $(m - a + 1)$ modulo $10^9 + 7$ while evaluating $F(a)$.

The model code follows exactly this flow and stores $K_c$ in an array (kk[c]).

6) Complexity

Per test case:

game DP over masks: $O(n^2 2^n)$ in direct form
threshold aggregation: $O(mn)$

Given $\sum 2^n \le 2^{20}$ and $\sum m \le 10^6$, this passes.