求组合数的板子 lucas相关
#include<cstdio> #include<cctype> inline void read(int &x){ char ch=getchar();x=0; for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0'; } typedef long long ll; const int mo=10007,N=1e5+9; int T,fac[N],inv[N],n,m; inline int ksm(int x,int k){ int ans=1; for(;k;k>>=1,x=1ll*x*x%mo)if(k&1)ans=1ll*ans*x%mo; return ans; } inline int C(int x,int y){ if(x<y)return 0; if(x<mo && y<mo)return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo; return 1ll*C(x%mo,y%mo)*C(x/mo,y/mo)%mo; } int main(){ read(T);fac[0]=1; for(int i=1;i<mo;i++)fac[i]=1ll*fac[i-1]*i%mo; inv[mo-1]=ksm(fac[mo-1],mo-2); for(int i=mo-2;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%mo;//a^(p-1)==1相当于消去了一个 for(;T;T--){ read(n),read(m),printf("%d\n",C(n,m)); } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9874669.html
相关资源：JAVA上百实例源码以及开源项目