この問題は、Relaxed Convolution と呼ばれるオンライン畳み込みアルゴリズムを用いて解くことができます。

[1] Relaxed Convolution の解説

Relaxed Convolution とは以下の問題を時間計算量 \(O(N (\log N)^2)\) で解くアルゴリズムです。

• \(A,B\) を多項式、\(a_n \coloneqq[x^n]A, b_n \coloneqq[x^n]B, c_n \coloneqq [x^n]AB\) とする（はじめに \(A,B\) は与えられていない）。
• \(i = 0,1,2, \ldots, N\) の順に以下のクエリをオンラインで処理する。
  • \(a_i, b_i\) が与えられるので、\(c_i\) の値を答える

\(2^M - 2 \geq N\) なる最小の正整数 \(M\) をとります。\(2^M-2 = O(N)\) です。説明の簡単のため、\(N\) を \(2^M-2\) で置き換えることによって \(N = 2^M - 2\) とします。

\(0 \leq p < M, 1 \leq q < 2^{(M-p)}\) を満たす整数 \((p,q)\) の組について
\(F_{p,q} \coloneqq (\displaystyle\sum_{i=q2^p-1}^{(q+1)2^p-2} A_ix^i)(\displaystyle\sum_{i=2^p-1}^{2^{p+1}-2} B_ix^i)\) および

\(G_{p,q} \coloneqq (\displaystyle\sum_{i=2^p-1}^{2^{p+1}-2} A_ix^i)(\displaystyle\sum_{i=q2^p-1}^{(q+1)2^p-2} B_ix^i)\) の値を管理することを考えます。

\(AB = \displaystyle\sum_{p=0}^{M - 1}\sum_{q=1}^{2^{(M-p)} - 1} F_{p,q} +\displaystyle\sum_{p=0}^{M - 1}\sum_{q=2}^{2^{(M-p)} - 1} G_{p,q}\) です。

\(F_{p,q}\) や \(G_{p,q}\) の値の計算は値が確定した瞬間、すなわち \(i = (q+1)2^p-2\) のクエリが与えられたときに行います。\(F_{p,q}\) や \(G_{p,q}\) の \((q+1) 2^p-3\) 次以下の係数は \(0\) であるため、\((q+1) 2^p-2\) 次以上の部分を計算すればよく、これは実質的に \(2^p\) 次多項式どうしの積であるため、FFT を用いることなどにより時間計算量 \(O(p2^p)\) で計算可能です。よって、各 \(p\) に対して \(F_{p,*}, G_{p,*}\) の形をした多項式の計算を \(O(p2^M)\) で行えるので、全体として \(O(M^22^M) = O(N(\log N)^2)\) で \(F_{p,q}, G_{p,q}\) たちを計算できます。
クエリに対する回答については、各 \(i, p\) に対し \((q+1)2^p-2 \leq i \leq (q+3)2^p-4\) を満たす \(q\) は高々 2 個しかないことから、\(O(\log N)\) 個の \(F_{p,q}\) や \(G_{p,q}\) の係数の足し合わせによって求めることができ（必要だがまた計算されていない \(F_{p,q}\) や \(G_{p,q}\) がないことに注意してください）、全体として \(O(N\log N)\) で処理できます。以上より、すべて合わせて \(O(N (\log N)^2)\) で処理が完了しました。

[2] 本問題の解法

\(F = \sum F_nx^n, G_n \coloneqq [x^n]F^2\) とします。\(F_n = A_n(\displaystyle\sum_{i<n} G_i)\) です。
Relaxed Convlution を用いることにより \(F_n\) の値から \(G_n\) の値を得ることができ、 \(G_i\) の累積和を管理しておくなどの方法で \(G_n\) の値から \(F_{n+1}\) の値を時間計算量 \(O(1)\) で求められるので、全体として \(F_1,F_2, \ldots, F_N\) を時間計算量 \(O(N(\log N)^2)\) で求めることができました。