アルゴリズム・数学

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

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

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

概要 この記事 の手法の一部を掘り下げたものです．少し適用例が集まったので記事化． 残念ながら，計算量オーダーの証明はしていないです，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 (1) 解説編 slope trick (2) 問題編 概要 凸関数の凸共役（Legendre-Fenchel 変換）とその性質について、軽くまとめます。さらに、slope trick による...

概要 下降冪 $(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}$ などと書いて、素数にわたる和や積...