Binomial Sums

$(\sum_{i=0}^{n}\binom{n}{i}i^k) \bmod p$ を $O(k + \log(n))$ で計算する。条件: $n \ge k$, $p$: 素数, $p > k$

Sum of Multiplicative Function

multiplicative function $f(n)$ に対し、$F(n) := \sum_{1 \le i \le n} f(i)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p) = g(p)$ とかけるとする。このとき、$F(n)$ を時間計算量 $O(n^{2/3})$、空間計算量 $O(\sqrt{n})$…

Find Linear Recurrence with Polynomial Coefficients

ある数列 $(a_0, a_1, a_2, \dots)$ が P-recursive (holonomic) であった場合に、$\sum_{i=0}^{k} f_{i}(n) \cdot a_{n-i} = 0$ ($n \ge k$) を満たすような($d$ 次以下の)多項式係数 $f_0, \cdots, f_k$ を見つける方法です。

格子点の数え上げの高速化

凸関数・凹関数で囲まれる範囲の格子点の個数の数え上げなどを、凸包を用いて高速化するテクニックです。半径 $n$ の円に含まれる格子点の個数を $O(n^{2/3})$ ほど、$1$ から $n$ までの約数の総和を $O(n^{1/3} \log{(n)})$ ほどで求めることができます。

Scary Sum

総和 $$ S(a, b, k) := \sum_{x=0}^{b-1} \left\lfloor\frac{ax}{b}\right\rfloor^k $$ を ${}\bmod{p}$(十分に大きな素数)で $O(k \log k \log(\min\{a, b\}))$ で求めます。ただし、$\gcd(a, b) = 1$ とします。

最小費用最大流の悪例題

蟻本に掲載されている最小費用流の実装で、$n$ を頂点数として、$O(2^{n/2} n^2 \log n)$ 時間かかる例題です。

二項係数 mod Prime Power

$\binom{n}{m} \bmod p^e$ を高速に解く。($n, m, p^e \lt 10^{300}$, $pe \lt 10^6$, $p$: 素数)

除算・剰余算の高速化

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

FFT (NTT) 関連

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