メモ

yukicoderでゆるふわgolf

きたまさ法

この記事ではきたまさ法の「気持ち」を多項式剰余を用いて説明します。
間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。
数式により厳密に議論を追いたい方は高速 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として本質的には何も変わらない)


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

ではこのことを念頭において次の問題を考えてみよう
問題:a_{n+2}=a_{n+1}+a_nという漸化式で与えられる数列がある。a_5a_0a_1を用いて表せ
答案:
a_5\\
=a_4+a_3\\
=(a_3+a_2)+a_3\\
=2a_3+a_2\\
=2(a_2+a_1)+a_2\\
=3a_2+2a_1\\
=3(a_1+a_0)+2a_1\\
=5a_1+3a_0

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

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

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

多項式

x^5=\\
x^3*(x^2-x-1)\\
 +x^2*(x^2-x-1)\\
 +2x*(x^2-x-1)\\
 +3*(x^2-x-1)\\
 +(5x+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)\\
 +(5a_1+3a_0)

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


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


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


○例題
問題:a_0=1,\ a_1=3,\ a_{n+2}=a_{n+1}+2a_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+4x+4\equiv 5x+6\\
x^8 \equiv (5x+6)^2=25x^2+60x+36\equiv 85x+86\\
x^{12} \equiv (85x+86)(5x+6)=425x^2+940x+516 \equiv 1365x+1366
よって
a_{12}=1365a_1+1366a_0=1365*3+1366*1=5461


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