アルゴリズム・数学

 

公開日
2021/05/04 素数に関する上からの評価(初等的な証明)
2021/03/29 Dirichlet 積と、数論関数の累積和
2021/03/16 slope trick (2) 問題編
2021/03/16 slope trick (1) 解説編
2020/08/11 [数学・numpy] 高速フーリエ変換(FFT)による畳み込み
2020/04/25 Segment Tree のお勉強(2)
2020/04/25 Segment Tree のお勉強(1)
2020/04/20 Euler Tour のお勉強
2020/04/05 Rolling Hashについて(survey + 研究)
2019/10/04 マトロイドのお勉強(JSC 2019 予選[E])
2019/06/30 $n$ 乗の計算
2019/06/16 Euclid の互除法
スポンサーリンク
アルゴリズム・数学

素数に関する上からの評価(初等的な証明)

概要 この記事では常に $p$ は素数を表すこととし、$i, k, n$ は整数、$x$ は実数を表すものとします。特に単に $\sum_{p\leq x}$ や $\prod_{p\leq x}$ などと書いて、素数にわたる和や積...
アルゴリズム・数学

Dirichlet 積と、数論関数の累積和

Dirichlet 級数と Dirichlet 積 $\N = \{1,2,3,\ldots\}$ を定義域とする関数 $a, b\colon \N\longrightarrow \C$ を、数論関数 (arithmetic...
アルゴリズム・数学

slope trick (2) 問題編

以下の、解説編を読んでいることを仮定とします。使う記号などは共通で、改めて説明していません。 前 → (1) 解説編 ABC 127 Absolute minima 解説編で述べたものをそのまま実装すれば...
アルゴリズム・数学

slope trick (1) 解説編

続き → (2) 問題編 ネタバレに配慮して、これが使える問題をまとめたものは、別記事 (2) 扱いとしています。 実装をしている具体的なコードについても、必要であれば (2) 問題編 における解答例を確認してください。 ...
アルゴリズム・数学

[数学・numpy] 高速フーリエ変換(FFT)による畳み込み

概要 「Python で競技プログラミングをやる」の文脈で、高速フーリエ変換を使うための基礎知識を整理します。 高速フーリエ変換自体は競技プログラミング以外の文脈でも重要なアルゴリズムですが、そうした需要に応えることは、本記事...
アルゴリズム・数学

Segment Tree のお勉強(2)

遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 概要 前回 → Segment Tree のお勉強 (1) を前提としています。 1点更新...
アルゴリズム・数学

Segment Tree のお勉強(1)

遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 遅延伝搬 Segment 木は後日、別記事で。 → Segment Tree のお勉強 (2) 概要 ...
アルゴリズム・数学

Euler Tour のお勉強

個人的に勉強したことを整理します。 新規性とか強い主張とかは、特にありません。 Euler Tour (1) DFS 順に探索して、通った頂点の列を記録する($1,2,3,4,3,2,5,2,1,6,1$)。(2...
アルゴリズム・数学

Rolling Hashについて(survey + 研究)

新しい数値設定や実装方法を提案するものではありません。 衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。 前提知識 本記事では簡単のため、アルファベットの集合を $\Sigma = \{0...
アルゴリズム・数学

[数学] 畳み込み入門:Dirichlet積とゼータ変換・メビウス変換

色々な畳み込み 一般的な理解から始めるのではなく,まずは具体例をざっと確認します. $A$ を数列とします.つまり,$A = $ のように数が非負整数で添字付けられていて並んでおり,その全体を $A$ と書きます. ※ ...
スポンサーリンク
タイトルとURLをコピーしました