atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 多項式・形式的べき級数 線形代数 線形漸化的数列 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} $$ を出力するような問題を考えます．より正確には，有限数列が与えられたとき，その列と矛盾しない定数係数線形漸化式のうち，位数が最小のものを求める問題を扱います．この問題を，本講座では復元問題と呼びます． 復元問題を解く代表的なアルゴリズムが Berlekamp–Massey アルゴリズムです．Berlekamp… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Flinearly_recurrent_sequence_reconstruction" title="線形漸化式の復元 - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/a/atcoder/20260619/20260619101617.png Hatena Blog https://hatena.blog 2026-06-19 10:16:16 rich https://info.atcoder.jp/entry/algorithm_lectures/linearly_recurrent_sequence_reconstruction 1.0 100%