Kitamasa 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /kitamasa-method#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /kitamasa-method#noredirect を利用してください。
name
Kitamasa 法
short description
Kitamasa 法とは、$k + 1$ 項間の線型漸化式で定まる数列の第 $N$ 項を $O(k^2 \log N)$ で求めるアルゴリズムである。高速 Kitamasa 法とは異なる。
input
$k + 1$ 項間の線型漸化式で定まる数列 $a$ の漸化式および初めの $k$ 項 $(a_0, a_1, \dots, a _ {k-1})$ および自然数 $N$
output
数列 $a$ の第 $N$ 項 $a_N$
time complexity
$O(k^2 \log N)$