[1] Rephrasing the problem

Assume that the process continues even if the number of PCT’s cards becomes \(M\) or greater.

Consider the sequence \(A_P\) defined as \(A_{P,i}:=(\)the number of PCT’s cards after \(i\) operations\()\) for \(0 \le i \le N\) when the process uses the permutation \(P\).

For a permutation \(P\) such that \(A_P = X\) to exist with a score of at least \(1\), all of the following conditions must be satisfied.

• $X_i + 1 \ge X_{i+1}$ for $0 \le i \le N-1$.
• $X_0=X_N=0$.
• $1 \le X_i \le M-1$ for $1 \le i \le N-1$.

If \(X\) satisfies this, the score of the permutation \(P\) such that \(A_P=X\) is \(\prod_{i=1}^{N-1} X_i\).

Here, consider the following sequences \(Y\) and \(Z\). Let \(p_1,p_2,\dots,p_k\) be the indices \(i\), in ascending order, such that \(0 \le i \le N-1\) and \(X_i + 1 > X_{i+1}\). Then, \(Y=(X_{p_1},X_{p_1+1},X_{p_2},X_{p_2+1},\dots,X_{p_k},X_{p_k+1})\) and \(Z=(X_{p_1},X_{p_1+1},X_{p_2},X_{p_2+1},\dots,X_{p_k})\) (\(1\)-indexed). For example, when \(X=(0,1,2,3,2,3,4,1,1,0)\), we have \(Y=(3,2,4,1,1,1,1,0)\) and \(Z=(3,2,4,1,1,1,1)\). Less formally, \(Y\) is the sequence of numbers of PCT’s cards before and after procedures where he eats one or more cards, and \(Z\) is obtained by removing the \(0\) at the end of \(Y\).

Here, we have \(\prod_{i=1}^{N-1} X_i = \frac{\prod_{i}^{} Z_{2i-1}!}{\prod_{i}^{} (Z_{2i}-1)!}\). Additionally, there are \(\frac{\prod_{i}^{} Z_{2i-1}!}{\prod_{i}^{} Z_{2i}!}\) permutations \(P\) such that \(A_P=X\). This can be derived by considering when PCT drew the cards that are being eaten in each procedure where he eats cards.

Therefore, one can see that the answer to the problem equals the answer to the following problem.

Find the sum of $\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!}$ over all sequences of non-negative integers $Z_1,Z_2,\dots,Z_{2K+1}$ that satisfy all of the conditions below.

• $\sum_{i=1}^{K} \left(Z_{2i-1}-Z_{2i}+1\right)+Z_{2K+1}+1 = N$
• $Z_{2i-1} \ge Z_{2i}(1 \le i \le K)$
• $Z_{2i} \le Z_{2i+1}(1 \le i \le K)$
• $1 \le Z_i \le M-1(1 \le i \le 2K+1)$

---

[2] Using the inclusion-exclusion principle

Among the above conditions, let us apply the inclusion-exclusion principle to \(Z_{2i} \le Z_{2i+1}(1 \le i \le K)\). Then, one can see that the answer can be found by solving the following problem for each \(1 \le N' \le N\).

Find the sum of $\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!} \times (-1)^{K}$ over all sequences of non-negative integers $Z_1,Z_2,\dots,Z_{2K}$ that satisfy all of the conditions below.

• $\sum_{i=1}^{K} \left(Z_{2i-1}+1\right) - \sum_{i=1}^{K} \left(Z_{2i}\right)=N'$
• $Z_{2i-1} \ge Z_{2i}(1 \le i \le K)$
• $Z_{2i} > Z_{2i+1}(1 \le i \le K-1)$
• $1 \le Z_i \le M-1(1 \le i \le 2K)$

(\(Z_{2K+1}\) at the end of the sequence should be handled separately.) Below, let us consider this problem.

To solve this, one can use dynamic programming by letting \(\mathrm{dp}[i][j][k]\) as follows. Consider the situation in which the part of \(Z\) consisting of \(i\) and greater values is already determined, and \(l \bmod 2 =j\) where \(Z_l\) is the end of that part. Then, \(\mathrm{dp}[i][j][k]\) is the sum of \(\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!}\) over all \(Z\) such that \(\left(\sum_{i=1}^{\lfloor \frac{l+1}{2} \rfloor} Z_{2i-1}+1\right) - \left(\sum_{i=1}^{\lfloor \frac{l}{2} \rfloor} Z_{2i}\right)=k\).

---

[3] Optimizing the computation

If we compute this whole table, the complexity will be \(\mathrm{O}(NM)\), but the transitions in \(\mathrm{dp}\) can be represented by a product of matrices whose entries are polynomials. That is, if we let \(\mathrm{dp}[i][j]=\sum_{i=0}^{\infty} \mathrm{dp}[i][j][k] x^k\), the transitions are as follows.

• From $\mathrm{dp}[i][0]$ to $\mathrm{dp}[i-1][0]$, there are two transitions:
  • Do nothing. The coefficient is $1$.
  • Add two $i$s at the end of $Z$. The coefficient is $-ix$.
• From $\mathrm{dp}[i][0]$ to $\mathrm{dp}[i-1][1]$, there is one transition:
  • Add one $i$ at the end of $Z$. The coefficient is $-(i!)^2x$.
• From $\mathrm{dp}[i][1]$ to $\mathrm{dp}[i-1][0]$, there is one transition:
  • Add one $i$ at the end of $Z$. The coefficient is $\frac{x}{i!(i-1)!}$.
• From $\mathrm{dp}[i][1]$ to $\mathrm{dp}[i-1][1]$, there is one transition:
  • Do nothing. The coefficient is $x$.

Thus, if we let \(V_i = \begin{pmatrix} 1-ix & -(i!)^2x \\ \frac{x}{i!(i-1)!} & x \end{pmatrix}\), \(\mathrm{dp}[1][i]\) is the \((1,i)\)-entry of \(V_{M-1}V_{M-2}\dots V_2V_1\).

One can compute this in \(\mathrm{O}(M\log^2 M)\) time if one merges the matrices in a way resembling a perfect binary tree.

---

[4] Summary

Since the subproblem in the inclusion-exclusion principle is solved, the answer to the original problem can be found by finding the inverse of a polynomial in \(\mathrm{O}(N \log N)\) time.

Therefore, the problem is solved in \(\mathrm{O}(N\log N + M\log^2 M)\) time.