组合数前缀和
对于上指标的求和,我们有:
对于下指标的求和:
没有
莫队
将
时间复杂度为
#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
*/
分治取模
如果
将答案看作是一个
答案为
然而就算我们得到了该多项式,求点值的过程也会爆炸。
这里有一个巧思:
那么设
建出线段树,对每个区间
考虑如何预处理:对于
直接计算即可,根据主定理,其时间复杂度为
现在要离线处理询问,将询问挂在叶节点
往左儿子递归时
上面的引理就派上用场了,再设
代码咕咕咕。