K - Inner Product Editorial by ytqm3
\(K < M\) の場合は、 fps の inv を用いて \(O((N+M)\log (N+M))\) で 計算できます。以下、 \(M \le K\) を仮定します。
次数が \(O(n)\) の線形回帰数列 \(f,g\) について、 \(\sum_{i=0}^k f_ig_{k-i}\) は畳み込みと Bostan-Mori 法などを用いて \(O(n\log n\log k)\) で求められます。このことを用いたいです。
ここで、漸化式 \(G_i = \sum_{k=1}^M D_kG_{i-k}\) を、 \(D_0=-1\) として \(\sum_{k=0}^M D_kG_{i-k} = 0\) と変形してみます。
この式は左右対称的であることと、 \(D_M\neq 0\) が制約で保証されていることより、 \(G_{i-M}=\sum_{k=0}^{M-1} \frac{-D_k}{D_M}G_{i-k}\) と書けます。以下、
ここで、 \(H := (G_K,G_{K-1},\ldots,G_0)\) としてみると、 \(H_t = \sum_{l=1}^M \frac{-D_{M-l}}{D_M} H_{t-l}\) のように書けます。
ここで、 \(F = (F_1,F_2,\ldots,F_M):=(\frac{-D_{M-1}}{D_M},\frac{-D_{M-2}}{D_M},\ldots,\frac{-D_0}{D_M})\) としてみると、 \(H_t = \sum_{l=1}^M F_lH_{t-l}\) という形になり、結局 \(G_K,G_{K-1},\ldots,G_{K-M+1}\) が列挙できれば最初に述べた畳み込みから Bostan-Mori 法などで \(O((N+M)\log(N+M)\log K)\) でほかの処理を行えます。
\(G_{K-M+1},G_{K-M+2},\ldots,G_K\) の列挙はここやここで触れられています。解説が見つけられなかったので、軽く解説を置いておきます。
詳細
Fiduccia のアルゴリズム(高速 Kitamasa 法)を活用します。このアルゴリズムを使えば $G_{K-M+1} = \sum_{i=0}^{M-1} x_iG_i$ を満たす $x$ を $O(M\log M\log K)$ で求めることができます。ここで、線形漸化式の性質より、 $G_{K-M+1+t} = \sum_{i=0}^{M-1} x_iG_{i+t}$ が成り立つことがわかります。 $G$ の先頭 $2M$ 項は適当に $P(x)/Q(x)$ と表示して fps の逆元を計算すれば $O(M\log M)$ で求まり、 $y := (x_{M-1},x_{M-2},\ldots,x_0)$ とすれば $G_{K-M+1+t} = \sum_{p+q=M-1+t} G_py_q$ と表現できますから、結局畳み込みによって $O(M\log M\log K)$ で $G_{K-M+1},G_{K-M+2},\ldots,G_K$ を列挙できます。以上より、この問題を \(O((N+M)\log (N+M)\log K)\) で解くことができました。
posted:
last update: