HDU - 6333 Problem B. Harvest of Apples （莫队）

There are nn apples on a tree, numbered from 11 to nn.
Count the number of ways to pick at most mm apples.

Input

The first line of the input contains an integer TT (1≤T≤105)(1≤T≤105) denoting the number of test cases.
Each test case consists of one line with two integers n,mn,m (1≤m≤n≤105)(1≤m≤n≤105).
Output

For each test case, print an integer representing the number of ways modulo 109+7109+7.Sample Input

Sample Output

16

924129523

题意：
给定多个n,m，求C(n,m)
思路:
数据范围比较大，不能进行预处理。
我们可以采用莫队算法解决这个查询问题。

当n变大时，按此试展开，再和原式相比较，便可以得出转换公式。
n变小同理。
k的变化直接加减即可。
注意：变化过程中，可能使n>m,这个时候计算C的函数直接返回0就好了。
逆元要预处理，否则会T。

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;

#define ls (t<<1)

#define rs ((t<<1)+1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int maxm = ;

const int inf = 2.1e9;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

struct node{

    int l,r;

    int id;

}a[maxm];

ll anss[maxm];

int block;

bool cmp(node a,node b){

    return (a.l/block!=b.l/block)?a.l<b.l:a.r<b.r;

}

int vis[];

ll q_pow(ll a,ll b){

    ll ans=;

    while(b){

        if(b&){ans*=a;ans%=mod;}

        a*=a;

        a%=mod;

        b>>=;

    }

    return ans;

}

ll cal[maxn];

ll inv[maxn];

ll C(int n,int m){

    if(n<||m<||m>n){return ;}

    return cal[n]*inv[m]%mod*inv[n-m]%mod;

}

int main()

{

    cal[]=;inv[]=;

    for(int i=;i<maxn;i++){

        cal[i]=cal[i-]*i;

        cal[i]%=mod;

        inv[i]=q_pow(cal[i],mod-);

        inv[i]%=mod;

    }

    int m;

    scanf("%d",&m);

    int mx=;

    for(int i=;i<=m;i++){

        scanf("%d%d",&a[i].l,&a[i].r);

        a[i].id=i;

        mx=max(mx,a[i].l);

    }

    block=sqrt(mx);

    sort(a+,a++m,cmp);

    ll L=,R=;

    ll ans=;

    for(int i=;i<=m;i++){

        while(L>a[i].l){

            ans+=C(L-,R);

            ans%=mod;

            ans*=q_pow(,mod-);

            ans%=mod;

            L--;

        }

        while(R<a[i].r){

            R++;

            ans+=C(L,R);

            ans%=mod;

        }

        while(L<a[i].l){

            ans*=;

            ans%=mod;

            ans-=C(L,R);

            ans+=mod+mod;

            ans%=mod;

            L++;

        }

        while(R>a[i].r){

            ans-=C(L,R);

            ans+=mod+mod;

            ans%=mod;

            R--;

        }

        ans%=mod;

        anss[a[i].id]=ans;

    }

    for(int i=;i<=m;i++){

        printf("%lld\n",anss[i]);

    }

    return ;

}

巴特西

HDU - 6333 Problem B. Harvest of Apples （莫队）

最新文章

热门文章