読者です 読者をやめる 読者になる 読者になる

階乗 mod 素数

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

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

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

Ad Infinitum 15

母関数成分を補足.

母関数解法

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

実数関連の問題

$\min _{1 \le x \le N} \{\alpha x + \beta\}$ 問題 yukicoder No.219 巨大数の概算 など色々.

Polynomial Sum

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

FFT (NTT) 関連

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