FFT と多項式乗算

任意 mod の多項式乗算を 4 回の FFT でやる方法。ここでは、mod は $2^{30}$ 以下を想定。

Wavelet Matrix 3D [2]

前回の実装を簡略化する。

Wavelet Matrix 3D

3 次元クエリに対応できる Wavelet Matrix を実装する。

最小費用流問題(Cost Scaling)[2]

前回の Cost Scaling の実装を改善する。

最大流(Dinic vs HI-PR)

最大流のアルゴリズムの Dinic と Highest Label Push Relabel (HI-PR) を比較する。

除算・剰余算の高速化

除算・剰余算の高速化のテクニック。

最小費用流問題(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{\min \{i \in \mathbb{N} \mid \{\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$ で計算することを前提とする。