HDU – 6333 Problem B. Harvest of Apples (莫队+组合数学)

题意：计算C(n,0)到C(n,m)的和，T(T<=1e5)组数据。

分析：预处理出阶乘和其逆元。但如果每次O(m)累加，那么会超时。

定义 S(n, m) = sigma(C(n,m))。有公式：S(n,m) = S(n,m-1) +C(n,m)以及S(n,m) = 2*S(n-1,m) – C(n-1,m)。

这样就可以在O(1)的时间中计算出S(n+1,m),S(n-1,m),S(n,m+1),S(n,m+1)。可以用莫队离线处理T组查询。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn =1e5+;
const int mod = 1e9+;
LL fac[maxn],inv[maxn];
LL rev2;
LL qpow(LL b,int n){
    LL res=;
    while(n){
        if(n&) res=res*b%mod;
        b = b*b%mod;
        n>>=;
    }
    return res;
}LL Comb(int n,int k)
{
    return fac[n]*inv[k]%mod *inv[n-k]%mod;
}void pre()
{
    rev2 = qpow(,mod-);
    fac[]=fac[]=;
    for(int i=;i<maxn;++i) fac[i]=i*fac[i-]%mod;
    inv[maxn-]=qpow(fac[maxn-],mod-);
    for(int i=maxn-;i>=;i--) inv[i]=inv[i+]*(i+)%mod;
}int pos[maxn];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];
LL res;
LL ans[maxn];inline void addN(int posL,int posR)
{
    res = (*res%mod - Comb(posL-,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-,posR))%mod *rev2 %mod;
}inline void delM(int posL,int posR)
{
    res = (res-Comb(posL,posR)+mod)%mod;
}int main()
{
    #ifndef ONLINE_JUDGE
         freopen("in.txt","r",stdin);
         freopen("out.txt","w",stdout);
    #endif
    int T,N,M,u,v,tmp,K;
    int a,b;
    pre();
    int block = (int)sqrt(1.0*maxn);
    scanf("%d",&T);
    for(int i=;i<=T;++i){
        scanf("%d%d",&Q[i].L,&Q[i].R);
        pos[i] = i/block;
        Q[i].id = i;
    }
    sort(Q+,Q+T+);
    res=;
    int curL=,curR=;
    for(int i=;i<=T;++i){
        while(curL<Q[i].L) addN(++curL,curR);           //ok
        while(curR<Q[i].R) addM(curL,++curR);           //ok
        while(curL>Q[i].L) delN(curL--,curR);           //ok
        while(curR>Q[i].R) delM(curL,curR--);           //ok
        ans[Q[i].id] = res;
    }
    for(int i=;i<=T;++i) printf("%lld\n",ans[i]);
    return ;
}