メモ

yukicoderでゆるふわgolf

テクニック

遅延セグメント木

この記事では遅延セグメント木の「気持ち」を説明します。 通常のセグメント木に関する知識を前提とします。 アルゴリズムの説明のみであり、実装については一切説明していません。 基本的には以下のサイトの記述を、自分好みにリライトしたものです。 beet-…

Tonelli–Shanks algorithm

この記事ではTonelli–Shanks algorithmの原理の「気持ち」を説明します。 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 ループ不変量に着目する考え方はmod_sqrtについて.md · GitHubを参考にしました。 (追記:上…

Berlekamp–Massey algorithm

この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数(母関数)を用いて説明します。 (日本語で詳しく説明しているサイトが見つからなかったので) 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 …

きたまさ法

この記事ではきたまさ法の「気持ち」を多項式剰余を用いて説明します。 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 数式により厳密に議論を追いたい方は高速 Kitamasa 法 - みさわめもなどをご覧ください。 アル…