注：ラフな解説です

\(\mathrm{O}(N^{1.69})\) で計算する方法を簡単に説明する。(余談だが、もっと計算量が本質的に良くなると予想している。だれか挑戦してみてください)

記法：\(F^{\langle n \rangle}\) を \(F\) を \(n\) 回関数合成したものとして定義する。例えば \(F(F) = F^{\langle 2 \rangle}\), \(F^{\langle -1 \rangle}\) が \(F\) の逆関数, \(F^{\langle 1/2 \rangle}\) が \(F\) の関数的平方根。また \(G(F)\) を \(G \circ F\) のように表す。

\(G\) をニュートン法で計算する。\(n \geq 2\) を仮定する。\(G(G) \equiv F \bmod{x^n}\) が成り立つ \(G\) を \(G+x^n H\) に更新することにすると、\(\text{mod }x^{2n-1}\) 上 (\(2n-1\) なのに注意！) において次式が成り立つ。 (2 行目から 3 行目の変形で \(2n-1\) なのが生きている。3 行目から 4 行目の前半はテイラー展開を利用している)

\[ \begin{aligned} F &\equiv (G+x^n H) \circ (G + x^n H) \\ &\equiv G \circ (G + x^n H) + (x^n H) \circ (G + x^n H) \\ &\equiv G \circ (G + x^n H) + (x^n H) \circ G \\ &\equiv G \circ G + (G' \circ G) x^n H + G^n (H \circ G) \end{aligned} \]

この式を満たす \(H\) を \(\text{mod }x^{n-1}\) 上で計算できればよい。整理して両辺を \(x^n\) で割ると

\[H \circ G + (G' \circ G) \left(\frac{x}{G}\right)^n H \equiv \frac{F-(G \circ G)}{G^n} \pmod{x^{n-1}}\]

を得る。よって多項式 \(B, U\) を適宜定義して置き換えると

\[H(G) + BH \equiv U \pmod{x^{n-1}}\]

を満たす \(H\) を計算するということになる。(この \(H\) は一意に定まる)

ここで \(n-2\) 次までの FPS を長さ \(n-1\) のベクトルとみなして考えてみる。すると \(H(G)\) も \(BH\) も \(H\) に対応するベクトルへの線形変換になる。この考えを深めて整理すると、結局ある正則行列 \(M_1, M_2\) が存在して次の関係が成り立つ。(\(w\) に対応する FPS が \(W\) だとする)

• \(M_1 w\) : \(W(G)\) の計算 \(\iff\) \(M_1^{-1} w\) : \(W(G^{\langle -1 \rangle})\) の計算
• \(M_2 w\) : \(BW\) の計算 \(\iff\) \(M_2^{-1} w\) : \(B^{-1} W\) の計算
• 求めたいものは \((M_1 + M_2) h = u\) を満たす \(h\)
• \(M_1 + M_2\) は正則 (\(H\) の一意性による)

ここで \((M_1 + M_2) h = u \iff (M_2^{-1} M_1 + I) h = M_2^{-1} u\) である。そして \(u \gets M_2^{-1} u, M = M_2^{-1} M_1\) とする。つまり次式を解く問題を考える。

\[(M+I) h = u\]

Black Box Linear Algebra (BBLA) で解くことを考える。そのために \(M+I\) の最小多項式を求めたい。さらにそのために乱数ベクトルを \(v\) として \(v^{T} u, v^{T} (M+I)u, \dots, v^{T} (M+I)^{2(n-1)-2} u\) を求めたい。少し考えると \(v^{T} u, v^{T} Mu, \dots, v^{T} M^{2(n -1)-2} u\) を求めれば容易な変形で所望のものを得られるのでこれを求める。

\(S=\lceil \sqrt{2n}\rceil\) 程度にとって \(v^{T} M^{i} u\) \((0 \leq i \lt S^2)\) を求めることにする。そして \(i \lt S\) の範囲は愚直に \(\mathrm{O}(S n \log^2 n)\) 掛けて計算することにする。
そして、\(M^S w\) という操作が多項式の世界ではある多項式 \(D\) を用いて \(D W(G^{\langle S \rangle})\) と表せることに気づくと、\(S \leq i \lt 2S\) の範囲の \(i\) については

\[ \begin{aligned} &v^T M^i u \\ &= v^T M^S M^{i-S} u\\ &= [x^{n-2}] \left((\mathrm{Rev}(V) D) \cdot (\mathrm{Poly}\left(M^{i-S} u\right)) \circ (G^{\langle S \rangle}) \right) \end{aligned} \]

となり、\(M^{i-S} u\) は前計算されているので \([x^{n-2}] (\mathrm{Rev}(V) D) (G^{\langle S \rangle})^i\) \((0 \leq i \lt n-1)\) を power projection で計算しておけば \(M^{i-S} u\) とのベクトルの内積ということになる。この方法を適切に繰り返していくことで、\(v^{T} M^{i} u\) \((0 \leq i \lt S^2)\) を \(\mathrm{O}(S)\) 回の関数合成および power projection と \(\mathrm{O}(n^2)\) 回の演算で計算できる。

その後、\(v^{T} M^{i} u\) を \(v^{T} (M+I)^{i} u\) に変換して Berlekamp-Massey で \(M+I\) の最小多項式 \(Z\) を \(\mathrm{O}(n^2)\) で求めた後に互除法で \(x\) の \(\text{mod }Z\) 上の逆元 \(R\) を求めて、そのベクトルを \(r\) とする。 すると

\[h = \sum_{i=0}^{|r|-1} r_i (M+I)^i u\]

が答えとなる。詳細は省略するがこれもまた \(\mathrm{O}(S)\) 回の関数合成により計算できる。(先に説明した手法と類似しているため詳細は省略する)

以上の手法により

\[H(G) + BH \equiv U \pmod{x^{n-1}}\]

を満たす \(H\) を \(\mathrm{O}(n^2 + n^{1.5} \log^2 n)\) で計算できたため、ニュートン法が \(\mathrm{O}(N^2 + N^{1.5} \log^2 N)\) で機能して問題を \(\mathrm{O}(N^2 + N^{1.5} \log^2 N)\) で解ける。ここで \(N^2\) かかっている箇所が 2 箇所あるが次のように計算量を落とせる。

• Berlekamp-Massey : Binary GCD の要領で \(\mathrm{O}(N \log^2 N)\) に計算量を落とせる
• ベクトル同士の直積：計算をまとめると \(\sqrt{N} \times N\) 行列と \(N \times \sqrt{N}\) 行列の積になるので \(\mathrm{O}(N^{\frac{\omega+1}{2}})\) に計算量を落とせる

よってすべてを \(\mathrm{O}(N^{\frac{\omega+1}{2}} + N^{1.5} \log^2 N)\) で計算できる。\(\omega \lt 2.38\) を満たす行列積アルゴリズムの存在が知られているため、これを利用すると \(\mathrm{O}(N^{1.69})\) でこの問題を解くことが出来る。

なお、writer は \(\mathrm{O}(N^2 + N^{1.5} \log^2 N)\) を実装している。制約下においては \(N^{1.5} \log^2 N\) の部分の定数倍がかなり重くボトルネックとなっていて、細部に至るまで適切な実装を行わないと TLE する可能性が高い点に注意が要る。