atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 多項式・形式的べき級数 線形代数 線形漸化的数列 C-recursive Berlekamp–Massey のアルゴリズム Reeds–Sloane のアルゴリズム 1. 概要 本講座では，正整数 $\boldsymbol{m}$ を法とする線形漸化式の復元問題を扱います． 線形漸化式の復元 では，数列から定数係数線形漸化式を復元する問題を，係数環が体である場合に解説しました．その場合のアルゴリズムの代表が Berlekamp–Massey アルゴリズムです．Berlekamp–Massey アルゴリズムは，入力列を先頭から順に処理し，各時点で数列が満たす最小位数の漸化式を更新していくアルゴリズムです． 一方で，競技プログラミングでもしばしば $\mathbb Z/m\mathbb Z$ を係数環として数列を扱います．$m$ が素数であればこれは体ですが，… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Flinearly_recurrent_sequence_reconstruction_mod" title="線形漸化式の復元（mod m） - 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/20260626/20260626105145.png Hatena Blog https://hatena.blog 2026-06-26 10:51:45 rich https://info.atcoder.jp/entry/algorithm_lectures/linearly_recurrent_sequence_reconstruction_mod 1.0 100%