(cache)きたまさ法

この記事ではきたまさ法の「気持ち」を多項式剰余を用いて説明します。
間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。
数式により厳密に議論を追いたい方は高速 Kitamasa 法 - みさわめもなどをご覧ください。
アルゴリズムの説明のみであり、実装については一切説明していません。

○きたまさ法とは何か
線形漸化式で与えられる数列の第 $K$ 項を高速に求めるアルゴリズム
より正確に言えば「 $N$ 項線形漸化式により与えられる数列の第 $K$ 項を $O (N^{2} \log K)$ で求めるアルゴリズム」
さらに、これを高速化した「高速きたまさ法」というアルゴリズムにより $O (N \log N \log K)$ で求めることも可能
以下では $N$ の数え方として、
例えばフィボナッチ数列 $F_{n + 2} = F_{n + 1} + F_{n}$ なら $N = 2$ 、
$a_{n + 100} = a_{n + 1} + a_{n}$ なら $N = 100$ とする。
（それぞれN=3, N=101として本質的には何も変わらない）

○線形漸化式と多項式剰余
・次数下げ
まずは次のような問題を考える
問題： $ϕ = \frac{1 + \sqrt{5}}{2}$ とするとき、 $ϕ^{5}$ を求めよ
この問題は、大学受験界隈などでは「次数下げ」という名前で知られる次のテクニックにより、計算の手間を少し減らすことができる
答案：
$ϕ^{2} = ϕ + 1$ を満たすので
$ϕ^{5} = ϕ^{3} (ϕ + 1) = ϕ^{4} + ϕ^{3} = ϕ^{2} (ϕ + 1) + ϕ^{3} = 2 ϕ^{3} + ϕ^{2} = 2 ϕ (ϕ + 1) + ϕ^{2} = 3 ϕ^{2} + 2 ϕ = 3 (ϕ + 1) + 2 ϕ = 5 ϕ + 3 = \frac{11 + 5 \sqrt{5}}{2}$

ではこのことを念頭において次の問題を考えてみよう
問題： $a_{n + 2} = a_{n + 1} + a_{n}$ という漸化式で与えられる数列がある。 $a_{5}$ を $a_{0}$ と $a_{1}$ を用いて表せ
答案：
$a_{5} = a_{4} + a_{3} = (a_{3} + a_{2}) + a_{3} = 2 a_{3} + a_{2} = 2 (a_{2} + a_{1}) + a_{2} = 3 a_{2} + 2 a_{1} = 3 (a_{1} + a_{0}) + 2 a_{1} = 5 a_{1} + 3 a_{0}$

上でやった問題とほとんど同様にして解けることがわかった。
これがきたまさ法を（多項式剰余で）理解するうえで大切な発想となる。

・次数下げと多項式剰余
さて、最初の問題に立ち返って、答案を次のように書き換える。
答案：
$x^{5}$ を $x^{2} - x - 1$ で割った商と余りを考えると
$x^{5} = (x^{3} + x^{2} + 2 x + 3) * (x^{2} - x - 1) + (5 x + 3)$ となる。
この式に $x = ϕ$ を代入することで
$ϕ^{5} = (ϕ^{3} + ϕ^{2} + 2 ϕ + 3) * (ϕ^{2} - ϕ - 1) + (5 ϕ + 3)$ となる。
$ϕ^{2} - ϕ - 1 = 0$ をなので第1項は消えて
$ϕ^{5} = 5 ϕ + 3$ となる。

ということで、最初の問題の方は多項式剰余を求める問題に帰着できることがわかる。
では数列の問題の方はどうだろうか。
本質的な部分だけ比較しよう。

多項式
$x^{5} = x^{3} * (x^{2} - x - 1) + x^{2} * (x^{2} - x - 1) + 2 x * (x^{2} - x - 1) + 3 * (x^{2} - x - 1) + (5 x + 3)$

数列
$a_{5} = (a_{5} - a_{4} - a_{3}) + (a_{4} - a_{3} - a_{2}) + 2 (a_{3} - a_{2} - a_{1}) + 3 (a_{2} - a_{1} - a_{0}) + (5 a_{1} + 3 a_{0})$

というわけで、なんと多項式の次数と添え字の部分がちょうど対応していることがわかる。
説明は省略するが、これはいつでも成り立つことがわかり、結局数列の場合も多項式剰余を求める問題に帰着できることになる。
これが最も本質的な部分。

○多項式剰余と繰り返し二乗法
繰り返し二乗法というテクニックを既知とする。
問題： $f (x)$ を多項式とし、その次数を $N$ としておく。 $x^{K} \mod f (x)$ を求めよ
（今までの例では、 $f (x) = x^{2} - x - 1$ であり、 $N = 2$ ）
多項式乗算を普通にやって $O (N^{2})$ 。
掛け算により $2 N$ 次くらいの多項式となるが、 $x^{N}$ 以上の次数の項については高次の項から順に次数下げを適用していくことで $O (N^{2})$ で適切な次数まで落とせる。
これを $O (\log K)$ 回やるので、全体では $O (N^{2} \log K)$ 。

○ウィニングラン
ここまでの説明で次の問題が解けたことになる。
問題：かくかくしかじかの線形漸化式で与えられる数列がある。 $a_{K}$ を $a_{0}, \dots, a_{N - 1}$ を用いて表せ
ということで、後は初期値として与えられている $a_{0}, \dots, a_{N - 1}$ の値を代入するとめでたく $a_{K}$ を得ることができる。

○例題
問題： $a_{0} = 1, a_{1} = 3, a_{n + 2} = a_{n + 1} + 2 a_{n}$ という漸化式で与えられる数列がある。 $a_{12}$ を求めよ
回答：
$f (x) = x^{2} - x - 2$ とおく。 $x^{12} \mod f (x)$ を求める。
$x^{2} \equiv x + 2 x^{4} \equiv (x + 2)^{2} = x^{2} + 4 x + 4 \equiv 5 x + 6 x^{8} \equiv (5 x + 6)^{2} = 25 x^{2} + 60 x + 36 \equiv 85 x + 86 x^{12} \equiv (85 x + 86) (5 x + 6) = 425 x^{2} + 940 x + 516 \equiv 1365 x + 1366$
よって
$a_{12} = 1365 a_{1} + 1366 a_{0} = 1365 * 3 + 1366 * 1 = 5461$

○高速きたまさ法
（この部分は筆者が正確な理解をしていないため、間違いがあれば指摘してください）
$O (N^{2})$ かかっている2つの部分について、次のテクニックを導入することで高速化できる。
・FFT：多項式の積を $O (N \log N)$ で求める
・モンゴメリ乗算： $2 N$ 次の多項式の剰余を $O (N \log N)$ で求める
これにより全体で $O (N \log N \log K)$ となる。

メモ

yukicoderでゆるふわgolf

きたまさ法