sotanishy's code snippets for competitive programming
Berlekamp-Massey のアルゴリズムは,与えられた数列を生成する最短の線形漸化式を求めるアルゴリズムである.
vector<T> berlekamp_massey(vector<T> a)
漸化式がわからない数列f
の最初のいくつかを愚直に求めて,Berlekamp-Masseyで漸化式を得て,高速 Kitamasa 法で第k
項を求めるという暴力的な方法がある.
auto coef = berlekamp_massey(f);
f.resize(coef.size());
reverse(coef.begin(), coef.end());
auto ans = kitamasa(f, coef, k);