题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6333
解题心得：
- 这个题可以说是十分精彩了，首先推组合数学的公式，其中一个很重要的公式是Cnm = Cmn-1 + Cm-1n-1 这个公式知道杨辉三角的都明白，但是一看发现似乎没啥用。但是可以以这个公式为基础继续推演下去。
- 设Snm = Cn1 + Cn2 + Cn3 + ...... Cnm 然后继续使用上面的基本公式可以化成
- Snm-1 = Snm - Cnm
Snm+1 = Snm + Cnm+1
Sn+1m = 2Snm - Cnm
Snm = （Sn+1m + Cnm)/2 - 这些个公式看起来没啥用，但是知道S的关系之间可以通过O(1)的复杂度来进行转化，这样就可以将105次询问离线化处理，也就是用莫队来维护。神奇阿，想破脑袋就是想不到阿。里面的除法取余的操作用逆元来处理，逆元可以先全与预处理出来。
// // ┏┛ ┻━━━━━┛ ┻┓ // ┃ ┃ // ┃ ━ ┃ // ┃ ┳┛ ┗┳ ┃ // ┃ ┃ // ┃ ┻ ┃ // ┃ ┃ // ┗━┓ ┏━━━┛ // ┃ ┃ 神兽保佑 // ┃ ┃ 代码无BUG！ // ┃ ┗━━━━━━━━━┓ // ┃ ┣┓ // ┃ ┏┛ // ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛ // ┃ ┫ ┫ ┃ ┫ ┫ // ┗━┻━┛ ┗━┻━┛ #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+100; const int MOD = 1e9+7; typedef long long ll; struct Query { ll n, m, B, pos, ans; }q[maxn]; ll unit, ans, fac[maxn], inv[maxn], t, rev2; ll quick_pow(ll a, ll b) { ll res = 1; while(b) { if(b&1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } void get_fac() { //预处理出阶乘和逆元 fac[0] = 1; fac[1] =1; for(int i=2;i<maxn;i++) { fac[i] = i * fac[i-1] % MOD; } //神奇的操作 inv[maxn-1] = quick_pow(fac[maxn-1], MOD-2); for(int i=maxn-2;i>=0;i--) { inv[i] = inv[i+1] * (i + 1) % MOD; } } bool cmp1(Query a, Query b) { if(a.B == b.B) return a.m < b.m; return a.B < b.B; } bool cmp2(Query a, Query b) { return a.pos < b.pos; } void init() { unit = sqrt(maxn); get_fac(); scanf("%lld", &t); for(int i=0;i<t;i++) { scanf("%lld%lld", &q[i].n, &q[i].m); q[i].B = q[i].n/unit; q[i].pos = i; } rev2 = quick_pow(2, MOD-2); sort(q, q+t, cmp1); } ll C(ll n, ll m) {//得到c(n, m)的组合 ll ans = fac[n] * inv[n-m] % MOD * inv[m] % MOD; return ans; } void addL(ll l, ll r) { ans = ((2 * ans % MOD) + MOD - C(l, r)) % MOD; } void cutL(ll l, ll r) { ans = (ans + C(l-1, r) % MOD) * rev2 % MOD; } void addR(ll l, ll r) { ans = (ans + C(l, r+1)) % MOD; } void cutR(ll l, ll r) { ans = (ans + MOD - C(l, r)) % MOD; } int main() { init(); ll l=1, r = 1; ans = 2; for(int i=0;i<t;i++) {//离线莫队处理 int L = q[i].n; int R = q[i].m; while(l < L) addL(l++, r); while(l > L) cutL(l--, r); while(r > R) cutR(l, r--); while(r < R) addR(l, r++); q[i].ans = ans; } sort(q, q+t, cmp2); for(int i=0;i<t;i++) { printf("%lld\n",q[i].ans); } return 0; }