\(O(N\log N)\) 時間で解けるので一応書いておきます。 公式解説を前提とします。

• \(\mod K\) ごとの結果をマージするところ

合計 \(N\) 次の多項式の総積ですが、かける多項式が高々 \(2\) 種しかない \(f^ig^j\) の形です。形式的べき級数の \(\log, \exp\) を利用するか、繰り返し二乗法を使うかのどちらかによって、\(O(N\log N)\) 時間でできます。

• \(B_i\) の計算

\(i!B_i = \sum_{j=0}^{N-1}j!A_j\cdot \frac{1}{(j-i)!}\)

です。\(C_j = A_{N-1-j}\) とおくと、これは

\(i!B_i = \sum_{j=0}^{N-1}C_{N-j}\cdot \frac{1}{(j-i)!}\)

と書けます。\(C\) と \(1/i!\) を畳み込むと \(N-1-i\) 項目に \(i!B_i\) がきます。結局、次が解ければよいです。

\(f_k\) が与えられていて、\(f_k = \sum_{i+j=k}g_i\cdot \frac{1}{j!}\) という関係式があるとき、\(g_i\) を求めよ

これは対応する形式べき級数をとると、\(f(x) = g(x)e^x\) の形です。\(g(x) = f(x)e^{-x}\) によって、\(f\) から \(g\) を計算できます（畳み込み \(1\) 回で、\(O(N\log N)\) 時間）。