\(a\) 円硬貨の払い方に関する母関数 \(F_a(x)\) は

\[F_a(x) = \sum_{i=0}^\infty x^{ia} = \frac{1}{1-x^a}\]

です。よって、\(1 \leq m \leq M-L+1\) を満たす範囲について

\[G_m(x) = F_m(x) F_{m+1}(x) \dots F_{m+L-1}(x)\]

とおくと \([x^N] G_m(x)\) が答えとなります。

ここで、\(N\) 次以下の係数を保持する形式的冪級数 \(f\) があったときに、

• \((1-x^a)f\) の \(N\) 次以下の係数を計算すること、および
• \(\frac{f}{1-x^a}\) の \(N\) 次以下の係数を計算すること

はともに \(\mathrm{O}(N)\) でできます。(前者は項ごとの乗算により計算できます。後者は割り算の筆算を考えると計算できます)

また、\(m \geq 2\) について

\[G_m(x) = G_{m-1}(x) \times \frac{1}{1-x^{m+L-1}} \times (1-x^{m-1})\]

が成り立つことが式変形によって確認できます。

よって、\(G_1(x)\) を \(L\) 回の除算で計算した後、\(G_{m-1}(x)\) の結果から \(G_m(x)\) を乗算・除算を 1 回ずつ行って計算することを繰り返すことで求めたい答えを全て得られます。計算量は \(\mathrm{O}(N^2)\) 程度で十分高速です。