階乗 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$ で計算することを前提とする。