(より詳しい解説は後日ブログで公開します)

\(F(t)\) を平行移動 \(F(t + G(0))\) に置き換えることによって \(G(0) = 0\) の場合に帰着しておきます．この処理は \(O(M \log(M))\) 時間です．

\(1\) 変数の場合の合成を簡単に復習します．求めたいのは \([t^{M-1}] \dfrac{\mathrm{rev}(F(t))}{1 - t G(x)} \bmod x^N\) です (\(\mathrm{rev}\) は多項式の係数列の reverse)．有理式 \(\dfrac{P(t,x)}{Q(t,x)}\) に対し，分子分母に \(Q(t, -x)\) をかけると \(t\) についての次数が \(2\) 倍になる代わりに \(x\) の奇数次が消えます．これを繰り返すと \([t^{M-1}] R_0 R_1 \cdots R_l \cdot \mathrm{rev}(F(t)) \bmod x^N\) という形に表され，\(l\) はおよそ \(\log_2(N)\)，\(R_e\) は \(t\) について \(2^e\) 次で，\(x\) については \(2^e\) の倍数次にのみ値をとります．この積を後ろから計算し，\([t^{M-1}]\) に届き得る部分だけを残していきます．\(O(N \log(N)^2)\) 時間です．

多変数の畳み込みも簡単に復習します．以降 \(j\) と書いたら問題文と同様に \(j = j_0 + N_0 j_1 + (N_0 N_1) j_2 + \cdots + (N_0 N_1 \cdots N_{K-2}) j_{K-1}\) とします．\(\chi(j) = \left\lfloor\dfrac{j}{N_0}\right\rfloor + \left\lfloor\dfrac{j}{N_0N_1}\right\rfloor + \cdots + \left\lfloor\dfrac{j}{N_0N_1 \cdots N_{K-2}}\right\rfloor\) とおくと，\(\chi(j+j') = \chi(j) + \chi(j')\) に限って畳み込みたいということになります．\(x_0^{j_0} \cdots x_{K-1}^{j_{K-1}}\) を \(x^j y^{\chi(j)}\) に置き換えた多項式で \({} \bmod (y^K - 1)\) での積を計算し\([y^0]\) を見るとちょうどほしいものが得られます．\(N = \prod_k N_k\) とおいて，\(O(K N \log(N))\) 時間です．

これらを組み合わせます．有理式 \(\dfrac{P(t,x_0,\ldots,x_{K-1})}{Q(t,x_0,\ldots,x_{K-1})}\) に対し，\(Q\) の \(t^i x_0^{j_0} \cdots x_{K-1}^{j_{K-1}}\) の係数のうち \(j\) が奇数となる箇所を \(-1\) 倍したもの，を分子分母にかけると分母は \(j\) が偶数の項のみ残ることがわかります．次は \(j \equiv 2 \pmod{4}\) の箇所を \(-1\) 倍にしたものをかけると分母は \(j\) が \(4\) の倍数の項のみ残ります．……とやっていくと上手くいくことがわかります．乗算は多変数畳み込み同様 \(y^{\chi(j)}\) を付けて \({} \bmod (y^K-1)\) で計算，とできます．これを \(O(\log(N))\) 回なので，\(O(K N \log(N)^2)\) 時間です．

これで定数倍がとてもよければ実行時間が間に合うかもしれませんが，高速化があります．

\(N_0 = \cdots = N_{K-1} = 2\) のときの方法を応用します．\(x_0\) について Taylor 展開 \(F(G(x_0, x_1, \ldots, x_{K-1})) = \sum_i F^{(i)}(G(0, x_1, \ldots, x_{K-1})) (G(x_0, x_1, \ldots, x_{K-1}) - G(0, x_1, \ldots, x_{K-1}))^i / i!\) を考えます．これは \(i < N_0\) のみ考えればよく，\(N_0\) 個の \(F^{(i)}\) と \(1\) 変数少ない多項式の合成と，\(N_0\) 回の \(K\) 変数畳み込みに帰着されます．これを繰り返したとき登場する部分問題の個数は \(1 + (N_0-1) + (N_1-1) + \cdots\) となっていきます．

閾値 \(B\) を設定し，\(N_0 \le \cdots \le N_{L-1} < B \le N_L \le \cdots \le N_{K-1}\) であるとき，\(x_0, \ldots, x_{L-1}\) までをこの微分の方法で処理し，\(x_L, \ldots, x_{K-1}\) については前に述べた方法で合成を求めることにします．\(B = \Theta(\log(N))\) ととると全体の時間計算量が \(O(N \log(N)^3 \log(\log(N))^{-1})\) になります．