2018 Multi-University Training Contest 4 B Harvest of Apples（hdu 6333）（莫队）

 

题目链接：hdu 6333 Problem B. Harvest of Apples

题意：求

思路：T和n的范围都是10的5次，比较大，一直在找规律，各种换算，找一个求得上述式子的快速的方法，但是没找到，看了题解后才知道莫队可以过。n与m变换的过程，需要得到两个式子：

这题T了很久，一直不知道为什么，结果发现是因为没有在 ll mod=1e9+7前面加上const，我：？？？？？这题数据真的是很严格了，这都行的？平常定义mod习惯写成#define mod （1e9+7） 但是由于要定义ll类型，就顺手定义成了ll mod=1e9+7，然后T了两个晚上，服气

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

struct node{
    ll n,m;
    ll id;
}q[100005];

int block;
bool cmp(const node &a,const node &b){
    if((a.m/block)!=(b.m/block))return a.m<b.m;
    return a.n<b.n;
}

ll mo(ll a,ll pp){
    if(a>=0&&a<pp)return a;
    a%=pp;
    if(a<0)a+=pp;
    return a;
}
ll powmod(ll a,ll b,ll pp){
    ll ans=1;
    for(;b;b>>=1,a=mo(a*a,pp)){
        if(b&1)ans=mo(ans*a,pp);
    }
    return ans;
}
ll b[100005],inv[100005];
ll C(int n,int m){
    if(n<m)return 0;
    if(m==n||m==0)return 1;
    return b[n]*inv[n-m]%mod*inv[m]%mod;
}
void init(){
    b[0]=1;
    for(int i=1;i<=100000;i++)b[i]=b[i-1]*i%mod;
    for(int i=0;i<=100000;i++)inv[i]=powmod(b[i],mod-2,mod);
}
int main(){
    init();
    int t;
    scanf("%d",&t);
    
    for(int i=1;i<=t;i++){ 
        scanf("%lld%lld",&q[i].n,&q[i].m);
        q[i].id=i;
    }
    block=sqrt(1.0*t);
    sort(q+1,q+1+t,cmp);
    ll ans[100005];
    memset(ans,0,sizeof(ans));
    ll N=1,M=1;
    ll temp=2;
    for(int i=1;i<=t;i++){
        while(q[i].n<N){
            temp=((temp+C(N-1,M))%mod*inv[2]%mod)%mod;//除2不能直接除，要用逆元！！ 
            N--;
        }
        while(q[i].n>N){
            temp=(2*temp-C(N,M)+mod)%mod;//加mod防止变成负数 
            N++;
        }
        while(q[i].m<M){
            temp=(temp-C(N,M)+5*mod)%mod;//防止变成负数 
            M--;
        }
        while(q[i].m>M){
            temp=(temp+C(N,M+1))%mod;
            M++;
        }
        ans[q[i].id]=temp;
    }
    for(int i=1;i<=t;i++){
        printf("%lld\n",ans[i]%mod);
    }
    return 0;
}