テクニック
Operations on Formal Power Series - Codeforcesを読め 終わり 以下では形式的べき級数環および形式的べき級数体にという概念を既知とし、その演算を具体的に計算機で計算するという部分に焦点を当てる。係数環は体とする。数学わかる人向けの説明： 形式的…
N以下の素数の個数π(N)をO(N^(3/4))で求めるアルゴリズムを説明する。 （真面目にやるとO(N^(2/3+ε))になったり、O(N^(2/3)/(logN)^2)になったりするらしいですが、それらはまだ理解していないので……）○DPテーブルの設計 DP[i][n]=(n以下の数のうちi番目の素…
この記事ではbaby-step giant-stepの「気持ち」を説明します。 アルゴリズムの説明のみであり、実装については一切説明していません。○baby-step giant-step algorithmとは 有限アーベル群上の離散対数問題を高速に解くアルゴリズム 平方分割でやる○正確に …
高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablogで誤りを指摘されたので、反省の意味を込めて自分でちゃんと考えた。 メビウスの反転公式 - Wikipediaを元にしているけど、よくわかってないので間違ってたら教えて 追記 全部隣接代数 (順序理論) - W…
![n4_t](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="11" height="10"><rect fill-opacity="0"/></svg>)
この記事ではGarnerのアルゴリズムの「気持ち」を説明します。 アルゴリズムの説明のみであり、実装については一切説明していません。 合同式の取扱にある程度慣れていることを前提とします（「適当な条件の下ではmodをとっても加減乗除ができる」と知ってい…
この記事では遅延セグメント木の「気持ち」を説明します。 通常のセグメント木に関する知識を前提とします。 アルゴリズムの説明のみであり、実装については一切説明していません。 基本的には以下のサイトの記述を、自分好みにリライトしたものです。 beet-…
この記事ではTonelli–Shanks algorithmの原理の「気持ち」を説明します。 間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。 ループ不変量に着目する考え方はmod_sqrtについて.md · GitHubを参考にしました。 （追記：上…
この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数（母関数）を用いて説明します。 （日本語で詳しく説明しているサイトが見つからなかったので） 間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。 …
この記事ではきたまさ法の「気持ち」を多項式剰余を用いて説明します。 間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。 数式により厳密に議論を追いたい方は高速 Kitamasa 法 - みさわめもなどをご覧ください。 アル…