メモ

yukicoderでゆるふわgolf

テクニック

ゼータ変換とメビウス変換

高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablogで誤りを指摘されたので、反省の意味を込めて自分でちゃんと考えた。 メビウスの反転公式 - Wikipediaを元にしているけど、よくわかってないので間違ってたら教えて 追記 全部隣接代数 (順序理論) - W…

Garnerのアルゴリズム

この記事ではGarnerのアルゴリズムの「気持ち」を説明します。 アルゴリズムの説明のみであり、実装については一切説明していません。 合同式の取扱にある程度慣れていることを前提とします(「適当な条件の下ではmodをとっても加減乗除ができる」と知ってい…

遅延セグメント木

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

Tonelli–Shanks algorithm

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

Berlekamp–Massey algorithm

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

きたまさ法

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