问题 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.
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).
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\n",ans[i]); return 0; }