\(M\) 以下の非負整数の値に対する母関数は

\[1 + x + \dots + x^M = \frac{1-x^{M+1}}{1-x}\]

です。これが \(N\) 個並んで総和が \(S\) ということは、

\[[x^S] \left( \frac{1-x^{M+1}}{1-x}\right)^N\]

を計算する問題ということになります。

\(\left( \frac{1-x^{M+1}}{1-x}\right)^N\) の部分を \((1-x^{M+1})^N\) と \(\frac{1}{(1-x)^N}\) に分解して考えましょう。

\[(1 - x^{M+1})^N = \sum_{i=0}^N \binom{N}{i} (-1)^i x^{(M+1)i}\]

\[\frac{1}{(1-x)^n} = \sum_{i=0}^\infty \binom{i+n-1}{n-1} x^i\]

です。よって適切な階乗前計算のもと \((1-x^{M+1})^N\) と \(\frac{1}{(1-x)^N}\) の \(S\) 次以下の係数は \(\mathrm{O}(1)\) で求められるので、\(i=0,1,\dots,S\) について

• \((1 - x^{M+1})^N\) の \(i\) 次の係数と
• \(\frac{1}{(1-x)^N}\) の \(S-i\) 次の係数の積

を計算して足し合わせれば答えを計算できます。計算量は \(\mathrm{O}(S)\) 程度で十分高速です。