HDOJ（6333-Problem B. Harvest of Apples(组合数学+莫队算法+逆元））

听闻少年二字，当与平庸相斥。这篇文章主要讲述HDOJ：6333-Problem B. Harvest of Apples(组合数学+莫队算法+逆元）相关的知识，希望能为你提供帮助。
【HDOJ（6333-Problem B. Harvest of Apples(组合数学+莫队算法+逆元））】题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6333

解题心得：

这个题可以说是十分精彩了，首先推组合数学的公式，其中一个很重要的公式是Cnm = Cmn-1 + Cm-1n-1 这个公式知道杨辉三角的都明白，但是一看发现似乎没啥用。但是可以以这个公式为基础继续推演下去。
设Snm = Cn1 + Cn2 + Cn3 + ...... Cnm 然后继续使用上面的基本公式可以化成
Sn m-1 = Sn m - Cn m
Sn m+1 = Sn m + Cn m+1
Sn+1 m = 2Sn m - Cn m
Sn m = （Sn+1 m + Cn m)/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 ",q[i].ans); } return 0; }