概要 項間の線形漸化式を持つ数列の第 項から 項までを の時間計算量で計算するアルゴリズムを説明する。 繰り返し二乗法と多項式の余り付き除算を用いる方法と比べると、定数倍が良いと思われる。 問題設定 が を満たすとする。 この記事内で多項式の除算を…