Problem B. Harvest of Apples 组合数求和（莫队没怎么看懂）

Problem B. Harvest of Apples Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 3775    Accepted Submission(s): 1450   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.   Input 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) .   Output For each test case, print an integer representing the number of ways modulo 109+7 .   Sample Input   2 5 2 1000 500   Sample Output   16 924129523   Source 2018 Multi-University Training Contest 4   Recommend chendu

莫队算法

莫队算法良心讲解

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
ll fac[maxn],inv[maxn];
ll rev2;
struct Query{
    int L,R,id,block;
    bool operator < (const Query &p)const{//按照分块排序，再按照右端点排序
        if(block == p.block) return R < p.R;
        return block < p.block;
    }
}Q[maxn];
ll res;
ll ans[maxn];
 
ll q_pow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}//快速幂取模
 
ll C(int n,int k){
    return fac[n] * inv[k] % mod * inv[n-k] % mod;
}//组合数公式
 
void init(){
    rev2 = q_pow(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] = q_pow(fac[maxn-1],mod-2);
    for(int i = maxn-2; i >= 0; i--){
        inv[i] = inv[i+1] * (i + 1) % mod;
    }//预处理阶乘的逆元（很巧妙，不需要每次求逆元了）
}
 
inline void addN(int posL,int posR){//因为传进来的posL已经加1了，所以求S(posL,posR)=2S(posL-1,posR)-C(posL-1,posR)
                                    //而S(posL-1,posR)就是上一次的结果res,故只需要算C(posL-1,posR)
    res = (2 * res % mod - C(posL-1,posR) + mod) % mod;
}
 
inline void addM(int posL,int posR){//因为传进来的posR已经自增完成，res是上一次的结果S(posL,posR-1)故只需要求C(posL,posR)
    res = (res + C(posL,posR)) % mod;
}
 
inline void delN(int posL,int posR){//因为传进来的是后缀自增，所以posL还是原来的值
                                    //那么新的S(posL-1,posR)=(S(posL,posR)+C(posL-1,posR))/2,其中S(posL,posR)就是res
    res = (res + C(posL-1,posR)) % mod * rev2 % mod;
}
 
inline void delM(int posL,int posR){//因为传进来的是后缀自增，所以posR还是原来的值
                                    //那么新的S(posL,posR-1)=S(posL,posR)-C(posL,posR),其中S(posL,posR)就是res
    res = (res - C(posL,posR) + mod) % mod;
}
 
int main(){
    int T;
    init();
    int len = (int)sqrt(maxn*1.0);
    scanf("%d",&T);
    for(int i = 1; i <= T; i++){
        scanf("%d%d",&Q[i].L,&Q[i].R);
        Q[i].id = i;//记录下查询顺序编号
        Q[i].block = Q[i].L / len;//块号
    }
    sort(Q+1,Q+1+T);//排序
    res = 2;
    int curL = 1,curR = 1;
    for(int i = 1; i <= T; i++){
        while(curL < Q[i].L) addN(++curL,curR);//需要算S(curL+1,curR)=2S(curL,curR)-C(curL,curR)
        while(curR < Q[i].R) addM(curL,++curR);//需要算S(curL,curR+1)=S(curL,curR)+C(curL,curR+1)
        while(curL > Q[i].L) delN(curL--,curR);//需要算S(curL-1,curR)=(S(curL,curR)+C(curL-1,curT))/2
        while(curR > Q[i].R) delM(curL,curR--);//需要算S(curL,curR-1)=S(curL,curR)-C(curL,curR)
        ans[Q[i].id] = res;
    }
    for(int i = 1; i <= T; i++){
        printf("%lld\n",ans[i]);
    }
    return 0;