HDU6333 Harvest of Apples

http://acm.hdu.edu.cn/showproblem.php?pid=6333

Problem Description
There are n apples on a tree, numbered from 1 to n.
Count the number of ways to pick at most m apples.

题意：T(10万)组询问，每次询问 ${\sum }_{i=0}^{m}C(n,i)$∑i=0m​C(n,i)
思路：
组合数式子推导：
$C(n,0)+C(n,1)+C(n,2)+...+C(n,m)$C(n,0)+C(n,1)+C(n,2)+...+C(n,m)
      $C(n,0)+C(n,1)+C(n,2)+...+C(n,m)$C(n,0)+C(n,1)+C(n,2)+...+C(n,m)
上下相加，得：
$C(n,0)+C(n+1,1)+C(n+1,2)+...+C(n+1,m)+C(n,m)=2\ast S(n,m)$C(n,0)+C(n+1,1)+C(n+1,2)+...+C(n+1,m)+C(n,m)=2∗S(n,m)
$C(n+1,0)+C(n+1,1)+C(n+1,2)+...+C(n+1,m)+C(n,m)=2\ast S(n,m)$C(n+1,0)+C(n+1,1)+C(n+1,2)+...+C(n+1,m)+C(n,m)=2∗S(n,m)
即 $S(n+1,m)+C(n,m)=2\ast S(n,m)$S(n+1,m)+C(n,m)=2∗S(n,m)

另外注意，这个莫队处理的最先并不是真正的区间，注意四个 $while$while要使得当前 $S(n,m)$S(n,m)满足实际意义，即 $n\>=m$n>=m，根据此来决定 $while$while的顺序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000+100;
const int mod = 1000000007;

int T,n,m,SIZE,ans[maxn];
ll fac[maxn],inv[maxn];
ll now_ans;
struct Query{
    int n,m,id;
    bool operator < (Query x){
        if(n/SIZE!=x.n/SIZE)return n/SIZE<x.n/SIZE;
        return m<x.m;
    }
}Q[maxn];

ll pow_mod(ll a,ll n,ll m)
{
    if(n==0)return 1;
    ll x=pow_mod(a,n/2,m);
    x=x*x%m;
    if(n&1)x=x*a%m;
    return x;
}

void init()
{
    SIZE=sqrt(T);
    fac[0]=1;
    for(int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<maxn;i++)inv[i]=pow_mod(fac[i],mod-2,mod);//注意inv[0]也要有，因为下面需要0!的逆元
}

ll C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main()
{
    //freopen("input.in","r",stdin);
    cin>>T;
    init();
    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);
    int n=Q[1].n,m=0;
    now_ans=1;
    for(int i=1;i<=T;i++)
    {   
        while(n<Q[i].n){
            now_ans=(2*now_ans-C(n,m)+mod)%mod;
            n++;
        }
        while(m>Q[i].m){
            now_ans=(now_ans-C(n,m)+mod)%mod;
            m--;
        }
        while(n>Q[i].n){
            now_ans=(now_ans+C(n-1,m))*inv[2]%mod;
            n--;
        }
        while(m<Q[i].m){
            now_ans=(now_ans+C(n,m+1))%mod;
            m++;
        }
        ans[Q[i].id]=now_ans;
    }
    for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
    return 0;
}