Half-GCD

線形漸化式の復元

多項式・形式的べき級数 線形代数 線形漸化的数列 C-recursive 行列累乗 Berlekamp–Massey のアルゴリズム Euclid の互除法 Half-GCD

1. 概要 本講座では，数列から定数係数線形漸化式を復元する問題について解説します． 例えば，Fibonacci 数列の先頭項 $$ S=(0,1,1,2,3,5,8,13) $$ を入力として，この数列が満たす漸化式 $$ S _ i = S _ {i-1} + S _ {i-2} $$ を出力するような問題を考え…