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 と多項式乗算

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

続きを読む