HDU6333 莫队+组合数

题目大意：

给定n m

在n个数中最多选择m个的所有方案

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LL long long

const int mod=1e9+;

const int N=1e5+;

/********组合数模板*********/

LL pow_mod(LL a, LL b) {

    LL res = 1LL; a %= mod;

    while(b){

        if(b & ) res = res * a % mod;

        a = a * a % mod;

        b >>= ;

    } return res;

}

LL inv(LL a) { return pow_mod(a, mod-); }

LL F[N], Finv[N];//F是阶乘，Finv是逆元的阶乘

void init() {

    F[] = Finv[] = 1LL;

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

        F[i] = F[i-] * 1LL * (LL)i % mod;

        Finv[i] = Finv[i-] * 1LL * inv(i) % mod;

    }

} // O(n)预处理

LL C(LL n, LL m) {

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

    return F[n] * 1LL * Finv[n - m] % mod * Finv[m] % mod;

} // O(1)获得组合数C(n,m)

/**************************/

LL res[N];

/********莫队*********/

int len;

struct Q {

    LL n,m;

    int block, id;

    bool operator <(const Q& q)const {

        if(block==q.block) return n<q.n;

        return block<q.block;

    }

}q[N];

void Mo(int t) {

    LL L=, R=, ans=1LL;

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

        LL l=q[i].n, r=q[i].m;

        while(L>l) ans=((ans+C(L-1LL,R))%mod*Finv[])%mod, L--;

        while(L<l) ans=(*ans%mod-C(L,R)+mod)%mod, L++;

        while(R<r) ans=(ans+C(L,R+))%mod, R++;

        while(R>r) ans=(ans-C(L,R)+mod)%mod, R--;

        res[q[i].id]=ans;

    }

}

/**************************/

int main()

{

    init(); len=sqrt(N);

    int t; scanf("%d",&t);

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

        scanf("%lld%lld",&q[i].n,&q[i].m);

        q[i].block=q[i].m/len; q[i].id=i;

    }

    sort(q,q+t);

    Mo( t);

    for(int i=;i<t;i++)

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

    return ;

}