求めたい値は、FPS を用いて

\[ [x^K] \prod_{i=1}^{N} (1 + a_ix) \]

と表すことが出来ます。ただ、この式を愚直に計算していると \(\mathrm{O}(N^2)\) かかってしまいます。

そこで、分割統治法を使います。\(f((a_1,a_2,\dots,a_k)) = \prod_{i=1}^{k} (1+a_ix)\) とします。この時、求めたい多項式は \(f((a_1,a_2,\dots,a_N))\) となります。ここで、\(f\) を以下のように計算することにします。

• \(k = 1\) なら \(1 + a_1x\) を返す。
• そうでないなら、\(m = \left \lfloor \frac{k}{2} \right \rfloor\) として、\(g=f((a_1,a_2,\dots,a_m)),h=f((a_{m+1},a_{m+2},\dots,a_k))\) を計算する。
• \(gh\) を畳み込みで計算して返す。

計算量を解析しましょう。\(f\) に補助的な変数 \(c\) を付け加えた \(f'((a_1,a_2,\dots,a_k),c)\) を考えます。返り値は \(f((a_1,a_2,\dots,a_k))\) と等しいです。ここで、\(f'\) は以下のように動作します。

• \(k = 1\) なら \(1 + a_1x\) を返す。
• そうでないなら、\(m = \left \lfloor \frac{k}{2} \right \rfloor\) として、\(g=f'((a_1,a_2,\dots,a_m),c+1),h=f'((a_{m+1},a_{m+2},\dots,a_k),c+1)\) を計算する。
• \(gh\) を畳み込みで計算して返す。

\(f'((a_1,a_2,\dots,a_N),0)\) を呼び出したとします。\(c = i\) であるような \(f'\) について \(gh\) を計算する部分の計算量の総和を考えると、\(g,h\) の長さの総和が \(2N\) で抑えられているので \(\mathrm{O}(N \log N)\) となります。また、\(c\) は \(\left \lceil \log_2(N) \right \rceil\) で抑えられるため、全体の計算量は \(\mathrm{O}(N \log^2 N)\) となります。