Binomial Sum mod 素数

二項係数の総和 $\left(\sum_{i=0}^{k} \binom{n}{i}\right) \bmod{p}$ を $O(\sqrt{p} \log{p})$ で求める。($0 \le k \le n \lt p$)

計算方法

$v := \lfloor\sqrt{k}\rfloor$, $f_m(x) := \prod_{i=1}^{m}(x+i)$, $g_m(x) := \sum_{i=1}^{m} \left(\prod_{j=1}^{i-1}(n+1-j-x) \cdot \prod_{j=i}^{m} (x+j)\right)$ とおくと、$$ \sum_{i=0}^{k} \binom{n}{i} = \frac{1}{f_v(0)} \left(g_v(0) + \frac{f_v(n-v)}{f_v(v)} \cdot \left(g_v(v) + \frac{f_v(n-2v)}{f_v(2v)}\cdot\left(g_v(2v) + \cdots \right) \right) \right) + \sum_{i=v^2}^{k} \binom{n}{i} $$ と変形できる。

よって、$f_v(iv)$, $f_v(n-(i+1)v)$, $g_v(iv)$ ($0 \le i < v$) を $O(\sqrt{k} \log{k})$ で計算できると十分。最後の総和は、これらの計算結果を用いて $O(\sqrt{k})$ で計算可能。(逆元計算の計算量は省いて表記)

ここで、多項式 $f_m(x)$ と $g_m(x)$ は以下の関係式を満たす。$$ \begin{aligned} f_{2m}(x) &= f_m(x) \cdot f_m(x+m)\\ g_{2m}(x) &= g_m(x) \cdot f_m(x+m) + g_m(x+m) \cdot f_m(n-m-x) \\ \end{aligned} $$

すると、$n! \bmod{p}$ を $O(\sqrt{p} \log{p})$ で求める方法(Lagrange 補間 + FFT)と同様にして、$f_m(0), f_m(v), \dots, f_m(mv)$, $g_m(0), g_m(v), \dots, g_m(mv)$ から $f_{2m}(0), f_{2m}(v), \dots, f_{2m}(2mv)$, $g_{2m}(0), g_{2m}(v), \dots, g_{2m}(2mv)$ を $O(m \log{m})$ で計算できる。$f_{2m+1}, g_{2m+1}$ も $f_{2m}, g_{2m}$ から $O(m)$ で計算できるので、$f_v, g_v$ は $O(\sqrt{k} \log{k})$ で計算できる。

よって、$\left(\sum_{i=0}^{k} \binom{n}{i}\right) \bmod{p}$ は $O(\sqrt{p} \log{p})$ で求まる。

その他

同様にして、$\left(\sum_{i=0}^{n} i!\right) \bmod{p}$ や $!n \bmod{p}$ (Montmort number) も $O(\sqrt{p} \log{p})$ で計算できる。

前者に関しては、$f_m(x) := \prod_{i=1}^{m} (x+i)$, $g_m(x) := \sum_{i=1}^m \left(\prod_{j=1}^{i} (x+j) \right)$ とおくと、$\sum_{i=0}^{n} i! = 1 + \sum_{i=0}^{v-1} \left( \prod_{j=0}^{i-1} f_v(jv) \right) \cdot g_v(iv) + \sum _{i=v^2+1}^{n} i!$ であり、$$
\begin{align*}
f_{2m}(x) &= f_m(x) \cdot f_{m}(x+m) \\
g_{2m}(x) &= g_m(x) + f_m(x) \cdot g_m(x + m) \\
\end{align*}
$$ を使えばいい。

上の式は、Kurepa's Conjecture に関連する。

では $3 \le p \le n$ の判定には、$O(n^2 / \log{n})$ かかると書かれているが、 $O(n^{3/2})$ ほどで判定できる。