[1]解の言い換え

もし途中で PCT 君の持っているカードの枚数が \(M\) 枚以上になったとしても操作を最後まで行うものとします。

順列 \(P\) を使い操作を行ったとき、\(0 \le i \le N\) に対し、\(A_{P,i}:=\) 「\(i\) 回操作を行った後の PCT 君の手札の枚数」と定義される数列 \(A_P\) を考えます。

\(A_P = X\) を満たす順列 \(P\) が存在し、かつスコアが \(1\) 以上になるためには \(X\) は以下の条件を全て満たす必要があります。

• $0 \le i \le N-1$ に対し、$X_i + 1 \ge X_{i+1}$
• $X_0=X_N=0$
• $1 \le i \le N-1$ に対し、$1 \le X_i \le M-1$

\(X\) が上記を満たすとき、\(A_P=X\) となる順列 \(P\) に対し \(P\) のスコアは \(\prod_{i=1}^{N-1} X_i\) です。

ここで、カードを \(1\) 枚以上食べたときの操作の操作前と操作後の PCT 君の手札の枚数を並べた数列 \(Y\) を考えます。\(Y\) は 1-indexed とします。\(Y\) の末尾は \(0\) となりますが、この \(0\) を消した数列を \(Z\) とします。

つまり、\(0 \le i \le N-1\) を満たす整数 \(i\) のうち、\(X_i + 1 > X_{i+1}\) を満たす \(i\) を昇順に \(p_1,p_2,\dots,p_k\) としたとき、\(Y=(X_{p_1},X_{p_1+1},X_{p_2},X_{p_2+1},\dots,X_{p_k},X_{p_k+1}),Z=(X_{p_1},X_{p_1+1},X_{p_2},X_{p_2+1},\dots,X_{p_k})\) となります。例えば、\(X=(0,1,2,3,2,3,4,1,1,0)\) のとき、\(Y=(3,2,4,1,1,1,1,0),Z=(3,2,4,1,1,1,1)\) です。

ここで、\(\prod_{i=1}^{N-1} X_i = \frac{\prod_{i}^{} Z_{2i-1}!}{\prod_{i}^{} (Z_{2i}-1)!}\) が成り立ちます。 また、\(A_P=X\) となる \(P\) の個数は \(\frac{\prod_{i}^{} Z_{2i-1}!}{\prod_{i}^{} Z_{2i}!}\) 個です。これは今手札にあるカードのうち、食べるものを何回目に引いたかを考えることにより導出できます。

よって、本問題の解は以下の問題の解と等しいことがわかります。

以下の条件を満たす非負整数列 $Z_1,Z_2,\dots,Z_{2K+1}$ に対して、$\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!}$ の総和を求めてください。

• $\left(\sum_{i=1}^{K} 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]包除原理の利用

上記の条件のうち、\(Z_{2i} \le Z_{2i+1}(1 \le i \le K)\) に対して包除原理を適用します。すると、以下の問題を \(1 \le N' \le N\) に対して解けばよいことがわかります。

以下の条件を満たす非負整数列 $Z_1,Z_2,\dots,Z_{2K}$ に対して、$\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!} \times (-1)^{K}$ の総和を求めてください。

• $\sum_{i=1}^{K} (Z_{2i-1}+1) - \sum_{i=1}^{K} (Z_{2i})=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}\) があるため扱いが少し変わりますが、ほぼ同じです。以降上記の問題を解くことを考えます。

この問題は、「\(\mathrm{dp}[i][j][k]= Z_l \ge i\) となる部分まで \(Z\) を確定させたとき、\(l \bmod 2 =j\) であり、\(\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\) であるような \(Z\) に対する \(\frac{\prod_{i}^{} Z_{2i-1}!^2}{\prod_{i}^{} (Z_{2i}-1)! \times Z_{2i}!}\) の総和」という動的計画法により解を求めることができます。

---

[3]計算の高速化

このまま全ての状態を求めると計算量は \(\mathrm{O}(NM)\) かかってしまいますが、上記の \(\mathrm{dp}\) は多項式を要素に持つ行列積として遷移を表すことができます。つまり、\(\mathrm{dp}[i][j]=\sum_{i=0}^{\infty} \mathrm{dp}[i][j][k] x^k\) としたとき、以下のように遷移できます。

• $\mathrm{dp}[i][0]$ から $\mathrm{dp}[i-1][0]$ への遷移は、以下の $2$ 通りです。
  • 何もしない。遷移の係数は $1$
  • $Z$ の末尾に $i$ を $2$ 個追加する。遷移の係数は $-ix$
• $\mathrm{dp}[i][0]$ から $\mathrm{dp}[i-1][1]$ への遷移は、以下の $1$ 通りです。
  • $Z$ の末尾に $i$ を $1$ 個追加する。遷移の係数は $-(i!)^2x$
• $\mathrm{dp}[i][1]$ から $\mathrm{dp}[i-1][0]$ への遷移は、以下の $1$ 通りです。
  • $Z$ の末尾に $i$ を $1$ 個追加する。遷移の係数は $\frac{x}{i!(i-1)!}$
• $\mathrm{dp}[i][1]$ から $\mathrm{dp}[i-1][1]$ への遷移は、以下の $1$ 通りです。
  • 何もしない。遷移の係数は $x$

よって、 \(V_i = \begin{pmatrix} 1-ix & -(i!)^2x \\ \frac{x}{i!(i-1)!} & x \end{pmatrix}\) としたとき、\(\mathrm{dp}[1][i]\) は \(V_{M-1}V_{M-2}\dots V_2V_1\) の \((1,i)\) 成分となります。

この計算は二分木のように行うことで \(\mathrm{O}(M\log^2 M)\) で行うことができます。

---

[4]まとめ

包除原理の部分問題が解けたため、多項式の逆元を \(\mathrm{O}(N \log N)\) で求めることにより元の問題の解を得ることができます。

よって、この問題を \(\mathrm{O}(N\log N + M\log^2 M)\) で解くことができました。