はじめに
最近Berlekamp-MasseyやBostan-Moriで殴れる問題をよく見るので、そのような問題をメモしていこうと思います。 以下の説明はお気持ちなので間違ってる可能性が大いにあります。もし間違っている点がありましたら教えていただけるとありがたいです。
この記事ではアルゴリズム自体の解説はしません。世の中にはたくさんわかりやすい記事があるので、そちらを参考にしてください。
また、殴れる問題を見つけたらコメントやtwitterなどで教えていただけるととても助かります！
Berlekamp-Massey ってなに？
線形漸化式で与えられる数列の最初の何項かがわかっている時に、その漸化式を求めるアルゴリズムです。 計算量は、求める線形漸化式が $d$ 項間線型漸化式のとき $Ο(d ^ 2)$ です。
Bostan-Mori ってなに？
$d$ 項間線型漸化式を満たす数列の $N$ 項目を $Ο(M(d) \log N)$ で求めるアルゴリズムです。 ここで、 $M(d)$ は $d$ 次多項式同士の積を求めるために必要な計算量です。
$\bmod$ が $998244353$ のときなどは NTT を用いることで $M(d)=d\log d$ となります。 $\bmod$ が $ 1000000007$ のときは (任意modNTT を用いない限り) $ M(d)=d ^ 2 $ となります。
使い方
以上の二つのアルゴリズムを組み合わせることで、線形漸化式の導出が容易ではない(もしくはめんどくさい)場合に、愚直な解法で数列の最初の何項かを求め、Berlekamp-Masseyで線形漸化式を求め、Bostan-Moriで数列の $N$ 項目を求めることで容易に問題を解ける場合があります。
以下ではその手法が使える問題のリストをあげます。(随時教えていただけるとありがたいです)。
殴れる問題一覧
- Cube (AtCoder)
OEISを見ると漸化式が乗っているので、Bostan-Moriを使うだけです。
- Tax Included Price (AtCoder)
周期性がありそうなので、線形漸化式だと思うと、上記の手法で殴れます。
この問題は、あまりを求めるわけではないので、適当に2つの $\bmod$ を選び、復元する操作が必要です。
- Many Bus Stops (easy) (yukicoder)
- Many Bus Stops (hard) (yukicoder)
このように、行列累乗っぽい問題は大体線形漸化式なので、上記の手法が使えます。
- Tetrahedron (mojacoder)
想定解法は対称性から状態を頑張ってまとめて行列のサイズを落とすものですが、この問題も殴ることができます。 愚直に最初の方を求めると、綺麗な漸化式が求まるのであとはやるだけです。
- Hanjo 2 (AtCoder)
- simple 門松列 problem Re:MASTER (yukicoder)
現在のFastest Codeは、これで殴ったものです。
- Next Rational (yukicoder)
線形漸化式であることを信じましょう。 信じるものは救われます。
- Roman Digits (codeforces)
周期性！(素振り)
頑張って計算すると $Ο(1)$ で解けますが、めちゃくちゃ大変です。
上記の手法で殴ると、とても簡単に解くことができます。 maspyさんの以下のブログが詳しいです。
- Good Sequence (yukicoder)
やるだけ
随時加筆します。
