最近多校考了一道与此有关的题，于是我进行了一些相关的学习。
Description
$$\sum_{i=0}^k {n \choose i}$$
## Solution
### 算法一：莫队
令 $f(n,k) = \sum_{i=0}^k {n \choose i}$。
若已知 $f(n,k)$，容易推出 $f(n,k+1)$。
若已知 $f(n,k)$，考虑能否推出 $f(n-1,k)$。注意到：
$$\sum_{i=0}^k {n-1 \choose i} + \sum_{i=0}^{k-1} {n-1 \choose i} = f(n,k)$$
从而
$$2f(n-1,k) - {n-1 \choose k} = f(n,k)$$
即
$$f(n-1,k) = \frac {f(n,k) + {n-1 \choose k}} {2}$$
从而，根据 $f(n,k)$，我们可以推出所有**与其相邻的位置**的答案。
莫队即可。
### 算法二：分治取模
这是我结合多校题解和 zak 的博客学懂的，感觉很妙。听魏老师说，它的名字叫做 **djq 分治**。
注意到 ${n \choose p} = \frac {n-p+1} {p} {n \choose p - 1}$。
令 $F_i(x) = \frac {x-i+1} {i}$（特别的，$F_0(x) = 1$），则一次查询的答案为
$$\sum_{i=0}^k \prod_{j=0}^i F_j(n)$$
考虑建出线段树，对于维护 $[l,r]$ 信息的节点，预处理：
- $\prod_{i=l}^r F_i(x)
-
\sum_{i=l}^r \prod_{j=l}^i F_j(x)
令 K = \max\{k\}，容易 O(K \log^2 K) 求出。
对于一次询问，我们将其挂在 [n,n]（线段树上的一个叶子）处。
考虑如何求出答案。
我们在线段树上 dfs，设目前 dfs 到了 [l,r] 处，我们需要记录 F(x) = \prod_{i=0}^{l-1} F_i(x) 及 G(x) = \sum_{i=0}^{l-1} \prod_{j=0}^i F_j(x)。
向左子区间递归，F(x),G(x) 不变。向右子区间递归，F(x),G(x) 会被更新，需要若干次多项式乘法，复杂度无法接受。
根据多点求值的经典套路，考虑在传入 F(x),G(x) 时，将它们均对 \prod_{n \in [l,r]} (x-n) 取模。这样一来，F(x),G(x) 的长度不超过子树内询问数。
时间复杂度 O(K \log^2 K)。
算法一的优势在于常数小、好写。
算法二的优势在于，时间复杂度与 n 无关，并且渐进复杂度更优。值得一提的是，若要求 \sum_{i=0}^k {n \choose a_i}（其中 a 单调不降），只能使用算法二。