アルゴリズム・数学

 

公開日
2024/02/01 グラフの数え上げ
2023/11/24 分割統治+FFT のよくある形のひとつ
2023/11/03 重心分解・1/3重心分解のお絵描き
2023/08/15 $K$ 個を選ぶ最適化における乱択アルゴリズム
2023/03/28 モノイド作用に関する離散対数問題
2023/02/11 分割統治による静的列の区間積クエリ
2022/10/29 slope trick (3) slope trick の凸共役
2022/07/27 Stirling 数を $p$ で割った余りの計算
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 の互除法
スポンサーリンク
アルゴリズム・数学

グラフ数え上げ

概要 「$N$ 頂点のグラフであって xx を満たすものはいくつありますか?」という種類の問題を扱います. いわゆる入力定数個の数え上げ問題です.「グラフが与えられるので条件を満たす部分グラフを数えよ」というタイプの問題は扱い...
アルゴリズム・数学

分割統治+FFT のよくある形のひとつ

概要 「分割統治FFT」というと特に みたいなタイプを指すような会話を少し見たことがあるのですが,どのくらい一般的な用語なのか分からず. 私は雑に,分割統治と FFT を組み合わせて答が求められる系のテクニックをすべて分割統...
アルゴリズム・数学

重心分解・1/3重心分解のお絵描き

お絵描きをしました。 重心分解 木の重心の定義や計算方法については省略します. 重心分解の図示 木の重心のひとつを求め,重心を取り除き連結成分に分けることを繰り返します. 各ステップにおいて,重心のひとつを根...
アルゴリズム・数学

$K$ 個を選ぶ最適化における乱択アルゴリズム

概要 この記事 の手法の一部を掘り下げたものです.少し適用例が集まったので記事化. 残念ながら,計算量オーダーの証明はしていないです,HELP. → 解決しました. 簡単な例 手法の説明のため,次の自明な問...
アルゴリズム・数学

モノイド作用に関する離散対数問題

概要 本記事では、次の離散対数問題の変種を扱います。 $X$ をモノイド、$S$ を集合とし、$X$ が $S$ に左作用しているとする。$x\in X$ および $s, t \in S$ および、正整数 $N$ が与えられる...
アルゴリズム・数学

分割統治による静的列の区間積クエリ

概要 本記事では、次の形の問題を扱います。 $X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ:区間 $[a,b)$ が与えられるので、...
アルゴリズム・数学

slope trick (3) slope trick の凸共役

slope trick (1) 解説編 slope trick (2) 問題編 概要 凸関数の凸共役(Legendre-Fenchel 変換)とその性質について、軽くまとめます。さらに、slope trick による...
アルゴリズム・数学

Stirling 数を $p$ で割った余りの計算

概要 下降冪 $(x)_n$、符号つき第 1 種 Stirling 数 $s(n,k)$、第 2 種 Stirling 数 $S(n,k)$ を次で定義します: $(x)_n = \prod_{0\leq i < n} ...
アルゴリズム・数学

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

概要 この記事では常に $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...
スポンサーリンク
タイトルとURLをコピーしました