组合数前缀和

· · 算法·理论

对于上指标的求和，我们有：

\sum_{i=m}^n\binom{i}{m}=\binom{n+1}{m+1}

对于下指标的求和：

\sum_{i=0}^m\binom{n}{i}

没有 \mathcal O(1) 的式子，不过有几种方法可以解决这个问题。

莫队

将 n,m 作为莫队的两个指针，维护当前的 \text{ans}。

时间复杂度为 \mathcal O(n\sqrt q)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, len = 320, p = 1e9 + 7, inv2 = 5e8 + 4;
int Q, fac[N], inv[N], blk[N], now = 2, ans[N];
int qpow(int a, int b) {
    int c = 1;
    while (b) { if (b & 1) c = (ll)c * a % p; a = (ll)a * a % p, b >>= 1; }
    return c;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % p;
    inv[n] = qpow(fac[n], p - 2);
    for (int i = n - 1; ~i; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % p;
    for (int i = 1; i <= n; i++) blk[i] = (i - 1) / len + 1;
}
int C(int n, int m) { return n < m ? 0 : (ll)fac[n] * inv[n - m] % p * inv[m] % p; }
struct query { int id, n, m; } q[N];
bool cmp(const query &a, const query &b) { return blk[a.n] == blk[b.n] ? ((blk[a.n] & 1) ? a.m < b.m : a.m > b.m) : a.n < b.n; }
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> Q;
    for (int i = 1; i <= Q; i++) q[i].id = i, cin >> q[i].n >> q[i].m;
    init(1e5);
    sort(q + 1, q + 1 + Q, cmp);
    for (int i = 1, n = 1, m = 1; i <= Q; i++) {
        while (m < q[i].m) now = (now + C(n, ++m)) % p;
        while (n < q[i].n) now = (now * 2ll - C(n++, m) + p) % p;
        while (m > q[i].m) now = (now - C(n, m--) + p) % p;
        while (n > q[i].n) now = ll(now + C(--n, m)) * inv2 % p;
        ans[q[i].id] = now;
    }
    for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}
/*
2
5 2
1000 500
*/

分治取模

如果 n 特别大怎么办？

将答案看作是一个 m 次多项式，即：

f(x)=\sum_{i=0}^m\dfrac{x^{\underline i}}{i!}

答案为 f(n)。

然而就算我们得到了该多项式，求点值的过程也会爆炸。

这里有一个巧思：f(n)=f(x)\bmod(x-n)，因为 x^i\bmod(x-n)=n^i。

那么设 F_i(x)=\dfrac{x-i+1}{i}（定义 F_0(x)=1），所求式即为：

\sum_{i=0}^m\prod_{j=0}^iF_j(n)

建出线段树，对每个区间 [l,r] 预处理 M_{[l,r]}(x)=\prod\limits_{j=l}^rF_j(n) 及 S_{[l,r]}(x)=\sum\limits_{i=l}^r\prod\limits_{j=l}^iF_j(n)。

考虑如何预处理：对于 M，直接将左右儿子的 M 乘起来即可；对于 S：

\begin{aligned} S_{[l,r]}(x)&=\sum_{i=l}^r\prod_{j=l}^iF_j(x)\\ &=\sum_{i=l}^{\text{mid}}\prod_{j=l}^iF_j(x)+\left(\sum_{i=\text{mid+1}}^{r}\prod_{j=\text{mid+1}}^iF_j(x)\right)\left(\prod_{j=l}^{\text{mid}}F_j(x)\right)\\ &=S_{[l,\text{mid}]}(x)+S_{[\text{mid}+1,r]}(x)M_{[l,\text{mid}]}(x) \end{aligned}

直接计算即可，根据主定理，其时间复杂度为 \mathcal O(n\log^2n)。

现在要离线处理询问，将询问挂在叶节点 [m,m] 上，类似线段树分治，设当前区间为 [l,r]，记录 M_{[0,l-1]}(x) 与 S_{[0,l-1]}(x)。

往左儿子递归时 M 和 S 不用改变，往右儿子递归时需要多次多项式乘法，复杂度就不幸地爆炸了。

上面的引理就派上用场了，再设 G_{[l,r]}(x) 表示区间 [l,r] 内挂上的所有询问 (n,m) 的 x-n 之积，将 M 和 S 在传入右节点时将其对 G_{[\text{mid}+1,r]}(x) 取模，即可保证其长度不超过子树内的询问个数。总时间复杂度为 \mathcal O(m\log^2 m)。

代码咕咕咕。