\(A_i :=\)「サイコロを \(i\) 回振ったとき、全ての目が出ているような通り数」と定義します。また、\(f(x) = \sum_{i=0}^{\infty} \frac{A_ix^i}{i!},g(x)=\sum_{i=0}^{\infty} A_ix^i\) とします。

\(f(x)= (e^x-1)^N\) です。\(f(x)\) から \(g(x)\) を求めます。ここで、EGF での \(e^{ax}\) は OGF では \(\frac{1}{1-ax}\) になることに注意します。

よって、\(f(x)=\sum_{i=0}^{N} \binom{N}{i} e^{ix} (-1)^{N-i}\) であるため、\(g(x) = \sum_{i=0}^{N} \frac{\binom{N}{i}(-1)^{N-i}}{1-ix}\) です。

よって、\(g(x)\) は \(N\) 次の多項式 \(p(x),q(x)\) を用いて \(g(x)=\frac{p(x)}{q(x)}\) と表すことができ、この \(p(x),q(x)\) は先程の \(g(x)\) の式を用いることで \(\mathrm{O}(N\log^2 N)\) で計算することができます。ここで、\(q(x)\) は因数に \((1-Nx)\) を持つことに注意してください。\(q(x) = (1-Nx)r(x)\) と置きます。

ここで、\(B_i:=\)「全ての目が出るまでに、ちょうどサイコロを \(i\) 回振る確率」と定義し、\(h(x) = \sum_{i=0}^{\infty} B_ix^i\) とします。このとき、\(h(x) = g\left(\frac{x}{N}\right)(1-x)\) が成り立ちます。よって、\(h(x) = \frac{p(\frac{x}{N})}{r(\frac{x}{N})}\) が成り立ちます。

ここで、確率母関数 \(F(x) = \sum_{i=0}^{\infty} a_ix^i\) に対して \(F(e^x)\) を考えます。\([x^k] F(e^x) = \sum_{i=0}^{\infty} [x^k] a_ie^{ix} = \sum_{i=0}^{\infty} \frac{a_i \times i^k}{k!}\) となります。よって、求めたい値は \(h(e^x)\) の \(x^M\) までの係数となります。

\(h(x) = \frac{p(\frac{x}{N})}{r(\frac{x}{N})}\) より、本問題は \(N\) 次多項式 \(C(x) = \sum_{i=0}^{N} c_ix^i\) に対して \(C(e^x)\) の \(M\) 次の係数までを求める問題に帰着されます。これは、\(\sum_{i=0}^{N} \frac{c_i}{1-ix}\) の \(M\) 次の係数までを求めればよいので、\(\mathrm{O}(N\log^2 N + M\log M)\) で解くことが出来ます。

よって、本問題を \(\mathrm{O}(N\log^2 N + M\log M)\) で解くことが出来ます。これは十分高速です。