2017-09-26から1日間の記事一覧

拡張ユークリッド互除法を使って特性多項式を求める

定数係数線形漸化式を持つような数列の先頭 n 項が与えられるので漸化式を求めよ、という問題を解く話。特性多項式を求める方針で攻められる。線形漸化式を持つタイプの数列は母関数が有理式になるので、mod x^2m 上で有理式近似を掛けるときれいに求まると…