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$ とします。

続きを読む