高速 Kitamasa 法 - みさわめも

要約 $k$ 階の線型漸化式 (フィボナッチ数列とか) の $N$ 項目を高速に求める. 競技プログラミング界隈で Kitamasa 法と呼ばれているやつは, 多項式の冪剰余. 高速多項式剰余で殴れば, $O(k \log k \log n)$. 実装だけしたいなら, 一番下の擬似コードを見るといいかも. 誤字脱字, ミス, ここがわからんとか, もっと綺麗な方法があれば, 教えて下さい. イントロ 初めの $k$ 項 $a_0, \dots, a_{k-1}$ と, $k$ 階線型漸化式 $$a_{n+k} = c_1 a_{n+k-1} + \dots + c_k a_{n}, \quad \forall n \ge 0$$ によって定まる数列 $a = \seq{a_n}_{n=0}^{\infty}$ を考える. $a_{n+k} = c_1 a_{n+k-1} + \dots +

[tar0_t]

線形漸化式の第N項目を高速に求める