多項式をマージする一般的(?)なテク
あぶすと
次数の和が$ Nであるような多項式の集合が与えられたときに,その総積を$ O(N\log^2 N)で得る方法について解説します.
ほんぶん
まず,次数それぞれ$ A, Bであるような多項式の積は FFT を用いて$ O(\max(A, B)\log \max(A, B))で得られることは有名です.
ここで問題になるのは FFT の計算量が次数の大きい方に依存しているということです,小さい方に依存する場合はデータ構造をマージする一般的なテク(デマテク)を用いて$ O(N\log^2 N)をかんたんに達成することができますが,今回はデマテクを用いると最悪$ O(N^2\log N)掛かってしまいます.
そこで,通常のマージテクでは小さい方を大きい方にマージしていましたが,その方法を少し変えて "次数が最小の二要素をマージする" としてみます.実はこれだけで$ O(N\log^2 N)を達成できます.
証明
まず,ある$ kが存在して$ 2^{k - 1} \le N < 2^k \le 2Nです.
次数$ 1の多項式が$ 2^{k}個あるとして考えます,すると計算量は以下のようになります.
$ O(\sum_{i = 0}^{k - 1} \frac{2^{k}}{2^{i + 1}}2^{i}\log(2^{i})) = O(2^{k}\log^2 (2^k))
$ kのとり方より$ O(2^k) = O(N)なので$ O(N\log^2N)です.
証明(noshi91 さんに教えてもらいました,ありがとうございます)
"併合が Ο(A + B) のときに Ο(NlogN) が言えればいい
ある要素 x が最終的なコストに加算される回数は、x を含む要素が併合された回数に等しい
x が一度併合された後、x 未満の要素は残っていない
よって 2 回併合されるうちに必ず大きさが 2 倍以上になり、Ο(logN) 回しか併合されず主張は示された"
別の手法によって同等の計算量を達成する方法(Ryuhei_Mori さんに教えてもらいました,ありがとうございます)
"k個の多項式の積を計算するとして、最終的な次数を n とすると、単純に k/2 個の多項式の集合2つに分ける分割統治で O(n log n log k) になると思います。
の Theorem 2.7
多項式に定数がないとすれば k <= n なので O(n (log n)^2) ですね。"
このテクを使って解ける問題
あとがき
うまい証明が思いつきませんでした.
テストと衝突事故を起こして短い記事になってしまった.