最小費用流問題 (Cost Scaling)

最小費用流問題を Cost Scaling を用いて $O(V^2E \log{(VC)})$ で解く。

Wolstenholme Prime の探索

$10^9

調和数 mod 素数

$\sum _{i=1}^{n} \frac{1}{i} \pmod{p}$ を計算量 $O(\sqrt{p} \log{p})$ で求める。

Binomial Sum mod 素数

二項係数の総和 $\sum_{i=0}^{k} \binom{n}{i} \pmod{p}$ を $O(\sqrt{p} \log{p})$ で求める。($0 \le k \le n

階乗 mod 素数

$n! \pmod{p}$ を計算量 $O(p^{1/2} \log{p})$ で求める。

一般最大マッチング / 一般最大重み付きマッチングの実装

一般最大マッチング $O(n^3)$ と一般最大重み付きマッチング $O(n^2m)$, $O(n^3)$ の C++ での実装例です。一般最大マッチングについては若干アルゴリズムを変更しているため、$\tilde{O}(n^3)$ になっているかもしれません。

母関数解法

母関数を用いて、機械的に解ける問題。

実数関連の問題

ある実数 $\alpha, \beta, \varepsilon$ と整数 $N$ が与えられたとき、 $$ \min_{1 \le i \le N} \{\alpha i + \beta\}, \\ \mathop{\text{arg min}}_{i > 0} \{\alpha i + \beta を求める問題について考える。ここで、$\{x\}$ は $x$ の小数部分を表すもの…

Polynomial Sum

djdolls さんの公式 QPOLYSUM - Editorial - CodeChef Discuss を、固有多項式を用いた一般的な方法で導出する。

FFT (NTT) 関連

FFT (NTT) を用いて $O(n^2)$ から $O(n \log{n})$ に高速化できるもの。 基本的に modulo $p$ で計算することを前提とする。