Harvest of Apples _Apple

追风赶月莫停留，平芜尽处是春山。这篇文章主要讲述Harvest of Apples相关的知识，希望能为你提供帮助。
问题 B: Harvest of Apples
时间限制: 1 Sec 内存限制: 128 MB
提交: 18 解决: 11
[提交] [状态] [讨论版] [命题人:admin] 题目描述 There are n apples on a tree, numbered from 1 to n.
Count the number of ways to pick at most m apples.
输入 The first line of the input contains an integer T (1≤T≤105) denoting the number of test cases.
Each test case consists of one line with two integers n,m (1≤m≤n≤105).
输出 For each test case, print an integer representing the number of ways modulo 109+7.
样例输入

2 5 2 1000 500

样例输出

16 924129523

莫队（分块），组合数学。
AC代码：

文章图片

#include< bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const int mod=1e9+7; ll fac[maxn],inv[maxn],ans[maxn]; ll rev2,res; int pos[maxn]; ll qpow(ll b,int n) { ll res=1; while(n) { if(n& 1) res=res*b%mod; b=b*b%mod; n> > =1; } return res; } ll Comb(int n,int k) { return fac[n]*inv[k]%mod*inv[n-k]%mod; } void pre() { rev2=qpow(2,mod-2); fac[0]=fac[1]=1; for(int i=2; i< maxn; ++i) fac[i]=i*fac[i-1]%mod; inv[maxn-1]=qpow(fac[maxn-1],mod-2); for(int i=maxn-2; i> =0; i--) inv[i]=inv[i+1]*(i+1)%mod; } struct Query { int L,R,id; bool operator < (const Query& p) const { if(pos[L]==pos[p.L]) return R< p.R; return L< p.L; } } Q[maxn]; inline void addN(int posL,int posR) { res=(2*res%mod-Comb(posL-1,posR)+mod)%mod; } inline void addM(int posL,int posR) { res=(res+Comb(posL,posR))%mod; } inline void delN(int posL,int posR) { res=(res+Comb(posL-1,posR))%mod*rev2%mod; } inline void delM(int posL,int posR) { res=(res-Comb(posL,posR)+mod)%mod; } int main() { int T,curL,curR; int block=(int)sqrt(1.0*maxn); pre(); scanf("%d",& T); for(int i=1; i< =T; ++i) { scanf("%d %d",& Q[i].L,& Q[i].R); pos[i]=i/block; Q[i].id=i; } sort(Q+1,Q+T+1); res=2; curL=1,curR=1; for(int i=1; i< =T; ++i) { while(curL< Q[i].L) addN(++curL,curR); while(curR< Q[i].R) addM(curL,++curR); while(curL> Q[i].L) delN(curL--,curR); while(curR> Q[i].R) delM(curL,curR--); ans[Q[i].id] = res; } for(int i=1; i< =T; ++i) printf("%lld ",ans[i]); return 0; }

View Code【Harvest of Apples】