Lucas定理的运用
$C(n,k)=C(n/Mod,k/Mod)*C(n\%Mod,k\%Mod)$
那么我们发现因为是求$C(n,0)+C(n,1)+...+C(n,k)$，对于其中的$C(n\%Mod,i)$,$0<=i<=k\%Mod$似乎会用很多次
然后推一下式子就发现这个可以处理成一个前缀和
然后就没了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int Mod=2333;
int t,C[Mod][Mod],Sum[Mod][Mod];
long long n,k;
void Pre(){
C[0][0]=1;
for(int i=1;i<Mod;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++){C[i][j]=C[i-1][j]+C[i-1][j-1];if(C[i][j]>=Mod)C[i][j]-=Mod;}
}
for(int i=0;i<Mod;i++)Sum[0][i]=1;
for(int i=1;i<Mod;i++){
Sum[i][0]=1;
for(int j=1;j<Mod;j++){Sum[i][j]=Sum[i][j-1]+C[i][j];if(Sum[i][j]>=Mod)Sum[i][j]-=Mod;}
}
}
int Lucas(long long n,long long k){return k==0?1:C[n%Mod][k%Mod]*Lucas(n/Mod,k/Mod)%Mod;}
int Cal(long long n,long long k){
if(k<0)return 0;
if(n<Mod)return Sum[n][k];
return (Lucas(n/Mod,k/Mod)*Sum[n%Mod][k%Mod]+Cal(n/Mod,k/Mod-1)*Sum[n%Mod][Mod-1])%Mod;
}
int main(){
freopen("4591.in","r",stdin);
freopen("4591.out","w",stdout);
scanf("%d",&t);
Pre();
while(t--){
scanf("%lld %lld",&n,&k);
printf("%d\n",Cal(n,k));
}
return 0;
}
评论 (0)
