题面

给定 TT 组 n,mn, m ，求：

∑i=0m(ni) \sum\limits_{i = 0}^{m} \binom{n}{i}

结果对 109+710^9 + 7 取模。

数据范围：

1≤T≤1051 \le T \le 10^5

1≤m≤n≤1051 \le m \le n \le 10^5

题目链接

分块

分析

虽然经过 O(n)\mathcal{O}(n) 的预处理后我们可以以 O(1)\mathcal{O}(1) 算出 (ni)\binom{n}{i} ，但是 O(Tn)\mathcal{O}(Tn) 的复杂度显然是不能被接受的。

那怎么办…… 我们希望复杂度能够降至 O(Tn)\mathcal{O}(T\sqrt{n}) 左右…… 分块？

分块的思想即大段维护，局部朴素。假设块长为 LL ，令数组 A[i][j]A[i][j] 代表 ∑k=0L⋅j(ik)\sum\limits_{k = 0}^{L \cdot j} \binom{i}{k} ，即前 jj 块的前缀和。

这样一来，对于给定的 n,mn, m ，令 S=⌊AL⌋S = \lfloor \frac{A}{L} \rfloor ，我们可以把待求的值分为两部分：

∑i=0m(ni)=A[n][S]+∑i=L⋅S+1m(ni) \sum\limits_{i = 0}^{m} \binom{n}{i} = A[n][S] + \sum\limits_{i = L \cdot S + 1}^{m} \binom{n}{i}

取 L=nL = \sqrt{n} 左右的话，每一次计算的复杂度就变成了 O(n)\mathcal{O}(\sqrt{n}) 级别。接下来我们需要在 O(n)\mathcal{O}(\sqrt{n}) 级别的复杂度内完成对 AA 的预处理。

我们考虑 A[i][j]A[i][j] 和 A[i−1][j]A[i - 1][j] 间能否在 O(1)\mathcal{O}(1) 内完成转移。

首先，我们知道：

(nm)=(n−1m)+(n−1m−1) \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}

那么相应地：

∑i=1m(ni)=(n0)+(n1)+⋯+(nm)=2⋅(n−10)+2⋅(n−11)+⋯+2⋅(n−1m−1)+(n−1m)=2⋅∑i=0m(n−1i)−(n−1m) \begin{aligned} \sum\limits_{i = 1}^{m} \binom{n}{i} & = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{m} \\ & = 2 \cdot \binom{n - 1}{0} + 2 \cdot \binom{n - 1}{1} + \dots + 2 \cdot \binom{n - 1}{m - 1} + \binom{n - 1}{m} \\ & = 2 \cdot \sum\limits_{i = 0}^{m} \binom{n - 1}{i} - \binom{n - 1}{m} \end{aligned}

所以也就有：

A[i][j]=2⋅A[i−1][j]−(i−1(j+1)⋅L−1) A[i][j] = 2 \cdot A[i - 1][j] - \binom{i - 1}{(j + 1) \cdot L - 1}

其中 (j+1)⋅L−1(j + 1) \cdot L - 1 也就是第 jj 块的最后一个元素。而这个组合数我们可以用预处理阶乘和逆元的方式在 O(1)\mathcal{O}(1) 内求得。

另外需要注意的是，在 L∣iL|i 时（也就是末尾出现了一个新的块时），需要手动处理一下： A[i][⌊iL⌋]=A[i][⌊iL⌋−1]+1A[i][\lfloor \frac{i}{L} \rfloor] = A[i][\lfloor \frac{i}{L} \rfloor - 1] + 1 。否则如果新出现的这一块一直是 00 的话后续转移会出问题。

另外，如果本题按照 N\sqrt{N} 取块长三百左右的话貌似会 MLE…… 我是取四百左右过的。

实现

完整参考代码

莫队

分析

当得知这道题还可以莫队时…… orz。

首先我们不妨记 S(n,m)=∑i=0m(ni)\mathcal{S}(n, m) = \sum\limits_{i = 0}^{m} \binom{n}{i} 。

由上我们已经得到了：

S(n,m)=2⋅S(n−1,m)−(n−1m) \mathcal{S}(n, m) = 2 \cdot \mathcal{S}(n - 1, m) - \binom{n - 1}{m}

那么反过来：

S(n,m)=12⋅(S(n+1,m)+(nm)) \mathcal{S}(n, m) = \frac{1}{2} \cdot (\mathcal{S}(n + 1, m) + \binom{n}{m})

好了，nn 的转移方式我们已经得到了。那么 mm 的转移呢？这不是很显然吗……

S(n,m)=S(n,m−1)+(nm) \mathcal{S}(n, m) = \mathcal{S}(n, m - 1) + \binom{n}{m}

S(n,m)=S(n,m+1)−(nm) \mathcal{S}(n, m) = \mathcal{S}(n, m + 1) - \binom{n}{m}

现在 nn 和 mm 的 O(1)\mathcal{O}(1) 转移方式都有了…… 我们好像真的可以用莫队了诶。真心佩服出题人的脑洞。

实现

完整参考代码