HDU 6333 Harvest of Apples (分块、数论)

题意：给出一个n和m，求C(0,n)+C(1,n)+.....+C(m,n)。(样例组数为1e5)

题解：首先先把阶乘和逆元预处理出来，这样就可O(1)将C(m,n)求出来了。但这样还是会超时，所以接下来要分块，每隔500个处理出C(1~m,n)的结果。然后还要知道一个性质 C(a,b) = ∑C(t1,x)*C(t2,y) （x+y<=b），这样我们就可以将给出的m和n分为两个组，其中一个组中元素的个数为500的倍数。然后我们对于另一个组枚举可能的t2然后求和，每次询问最大的操作次数就变成了500次。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const LL mod = 1e9 + ;

 typedef pair<int,int> P;

 const int MAX_N = 1e5+;

 int N,M,T,S;

 LL Jc[MAX_N];

 LL ni_[MAX_N];

 LL tran[][MAX_N];

 LL tr[][];

 //费马小定理求逆元

 LL pow(LL a, LL n, LL p)    //快速幂 a^n % p

 {

     LL ans = ;

     while(n)

     {

         if(n & ) ans = ans * a % p;

         a = a * a % p;

         n >>= ;

     }

     return ans;

 }

 LL niYuan(LL a, LL b)   //费马小定理求逆元

 {

     return pow(a, b - , b);

 }

 void calJc()    //求maxn以内的数的阶乘

 {

     Jc[] = Jc[] = ;

     for(LL i = ; i < MAX_N; i++)

         Jc[i] = Jc[i - ] * i % mod;

 }

 void calni(){

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

         ni_[i] = niYuan(Jc[i],mod);

     }

 }

 LL C(LL a, LL b)    //计算C(a, b)

 {

     return Jc[a] * ni_[b] % mod

         * ni_[a-b] % mod;

 }

 void init(){

     for(int i=;i<MAX_N/;i++){

         for(int j=;j<MAX_N;j++){

             tran[i][j] = C(*i,j);

             if(j>) tran[i][j] = (tran[i][j] + tran[i][j-])%mod;

         }

     }

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

         for(int j=;j<;j++){

             tr[i][j] = C(i,j);

         }

     }

 }

 int main(){

     calJc();

     calni();

     init();

     //cout<<"OK"<<endl;

     cin>>T;

     while(T--){

         LL a,b;

         scanf("%lld%lld",&a,&b);

         LL ans = ;

         if(a < ){

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

                 ans = (ans + tr[a][i])%mod;

         }

         else{

             LL t1 = a / ;

             LL t2 = a - t1*;

             for(int i=;i<=min(b,t2);i++){

                 ans = (ans + tr[t2][i]*tran[t1][min(b - i,t1*)])%mod;

             }

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

HDU 6333 Harvest of Apples (分块、数论)

最新文章

热门文章