[ 2018 Multi-University Training Contest 4 ] [ HDU6333 ] Harvest of Apples

        题目大意：求\(\sum_{i=0}^m{C_n^i}\)，数据组数\(T \leq 10^5 \)，\( 1 \leq m \leq n \leq 10^5 \)。

        题解：公式搞了半天搞不出来，结果是莫队做...

        m加减1很容易处理出来，利用\(C_{n+1}^m = C_n^{m-1} + C_n^m\)也可以很容易搞出n加减1的情况。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,Bsize=300,mo=1e9+7;

struct Query
{
	int n,m,id;
}Q[maxn];

bool cmpnm(const Query &a,const Query &b) {
	if (a.n/Bsize != b.n/Bsize) return a.n/Bsize < b.n/Bsize;
	return a.m<b.m;
}

long long inv[maxn];
int ans[maxn];
int T;

int main()
{
	inv[0]=inv[1]=1;
	for (int i=2;i<maxn;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	scanf("%d",&T);
	for (int i=1;i<=T;i++) scanf("%d%d",&Q[i].n,&Q[i].m),Q[i].id=i;
	sort(Q+1,Q+1+T,cmpnm);
	for (long long i=1,n=0,m=0,nowc=1,res=1;i<=T;i++)
	{
		long long nown=Q[i].n,nowm=Q[i].m;
		while (n<nown)
			res=(res*2-nowc+mo)%mo,nowc=nowc*(n+1)%mo*inv[n+1-m]%mo,n+=1;
		while (n>nown)
			nowc=nowc*(n-m)%mo*inv[n]%mo,res=(res+nowc)%mo*inv[2]%mo,n-=1;
		while (m<nowm)
			nowc=nowc*(n-m)%mo*inv[m+1]%mo,res=(res+nowc)%mo,m+=1;
		while (m>nowm)
			res=(res-nowc+mo)%mo,nowc=nowc*m%mo*inv[n-m+1]%mo,m-=1;
		ans[Q[i].id]=res;
	}
	for (int i=1;i<=T;i++) printf("%d\n",ans[i]);
	return 0;
}