Bzoj 4591: [Shoi2015]超能粒子炮·改数论,Lucas定理,排列组合

4591: [Shoi2015]超能粒子炮·改

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 178 Solved: 70
[Submit][Status][Discuss]

Description

曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明：超能粒子炮·改--一种可以发射威力更加

强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮，在威力上有了本质的提升。它有三个参数n，k。它会

向编号为0到k的位置发射威力为C(n,k) mod 2333的粒子流。现在SHTSC给出了他的超能粒子炮·改的参数，让你求

其发射的粒子流的威力之和模2333。

Input

第一行一个整数t。表示数据组数。

之后t行，每行二个整数n，k。含义如题面描述。

k<=n<=10^18，t<=10^5

Output

t行每行一个整数，表示其粒子流的威力之和模2333的值。

Sample Input

1
5 5

Sample Output

HINT

Source

By 佚名上传

题解：

Lucas定理：C(n,k)%p=(C(n/p,k/p)*C(n%p,k%p))%p (p为质数)

C(n,k)%2333=C(n/2333,k/2333)*C(n%2333,k%2333)

分两种部分考虑：

设k=k1*2333+k2 (0≤k1,k2)

1.对于k1部分

C(n,0)……C(n,2332)

=C(n/2333,0)*C(n%2333,0)+C(n/2333,0)*C(n%2333,1)+……+C(n/2333,0)*C(n%2333,2332) = C(n/2333,0)*(∑C(n%2333,i)(0≤i≤2332)) ==> 2333个

C(n,2333)……C(n,4665)

=C(n/2333,1)*C(n%2333,0)+C(n/2333,1)*C(n%2333,1)+……+C(n/2333,1)*C(n%2333,2332) = C(n/2333,1)*(∑C(n%2333,i)(0≤i≤2332)) ==> 2333个

C(n,4666)……C(n,6998)

=C(n/2333,2)*C(n%2333,0)+C(n/2333,2)*C(n%2333,1)+……+C(n/2333,2)*C(n%2333,2332) = C(n/2333,2)*(∑C(n%2333,i)(0≤i≤2332)) ==> 2333个

C(n,6999)……C(n,9331)

=C(n/2333,3)*C(n%2333,0)+C(n/2333,3)*C(n%2333,1)+……+C(n/2333,3)*C(n%2333,2332) = C(n/2332,3)*(∑C(n%2333,i)(0≤i≤2332)) ==> 2333个

…………

所以k1部分的总和sum=(∑C(n%2333,i)(0≤i≤2332))*(∑C(n/2333,j)(0≤j≤k1-1))

2.对于k2部分

C(n,k1*2333)……C(n,k)

=C(n/2333,k1)*C(n%2333,0)+C(n/2333,k1)*C(n%2333,1)+……+C(n/2333,k1)*C(n%2333,k%2333) ==> k%2333+1个

=C(n/2333,k1)*(∑C(n%2333,i)(0≤i≤k%2333))

由以上可得ans=(∑C(n%2333,i)(0≤i≤2332))*(∑C(n/2333,j)(0≤j≤k1-1))+C(n/2333,k1)*(∑C(n%2333,i)(0≤i≤k%2333))

预处理 S(n,k)=∑C(n,i)(0≤i≤k),化简ans=S(n%2333,2332)*(∑C(n/2333,j)(0≤j≤k1-1))+C(n/2333,k1)*S(n%2333,k%2333)

因为n%2333一定小于2333,所以可以用二维数组S(n,k)表示。但 ∑C(n/2333,j)(0≤j≤k1-1) 中n/2333可能很大，无法用二维数组存储，所以不把 ∑C(n/2333,j)(0≤j≤k1-1) 化简为 S(n/2333,k1-1)。但是可以发现 ∑C(n/2333,j)(0≤j≤k1-1) 与要求的最终答案的公式的格式 ∑C(n,i)(0≤i≤k) 一样，所以可以递归求解。另外ans中的C(n/2333,k1)可以用Lucas定理求解。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define MOD 2333

 LL jc[MOD+],C[MOD+][MOD+],S[MOD+][MOD+];

 LL read()

 {

     LL s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 LL mod(LL k,LL k1){return k-(k/k1)*k1;}

 void cljc()

 {

     jc[]=1LL;

     for(int i=;i<=MOD;i++)jc[i]=mod(jc[i-]*i,MOD);

 }

 void clC()

 {

     int i,j;

     C[][]=1LL;

     for(i=;i<=MOD;i++)

     {

         C[i][]=C[i][i]=1LL;

         for(j=;j<i;j++)C[i][j]=mod(C[i-][j]+C[i-][j-],MOD);

     }

     for(i=;i<=MOD;i++)

     {

         S[i][]=1LL;

         for(j=;j<=MOD;j++)S[i][j]=mod(S[i][j-]+C[i][j],MOD);

     }

 }

 LL ksm(LL bb,LL pp,LL kk)

 {

     LL s=1LL;

     while(pp>)

     {

         if(pp%!=)s=mod(s*bb,kk);

         pp/=;

         bb=mod(bb*bb,kk);

     }

     return s;

 }

 LL Comb(LL n,LL m,LL p)

 {

     if(m>n)return 0LL;

     if(m>n-m)m=n-m;

     return mod(jc[n]*ksm(mod(jc[m]*jc[n-m],p),p-,p),p);

 }

 LL Lucas(LL n,LL m,LL p)

 {

     if(m==0LL)return 1LL;

     return mod(/*Comb(mod(n,p),mod(m,p),p)*/C[n%p][m%p]*Lucas(n/p,m/p,p),p);

 }

 LL getans(LL n,LL m,LL p)

 {

     if(m<0LL)return 0LL;

     return mod(mod(S[mod(n,)][]*getans(n/,m/-,p),p)+mod(Lucas(n/,m/,p)*S[mod(n,)][mod(m,)],p),p);

 }

 int main()

 {

     LL T,n,k;

     cljc();

     clC();

     T=read();

     while(T--)

     {

         n=read();k=read();

         printf("%lld\n",getans(n,k,MOD));

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }

2333