题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2982
明明是lucas定理裸题……
非常需要注意C( )里 if ( n<m ) return 0; ！！！！！
可以预处理阶乘和其逆元，也可以现求。现求阶乘逆元的话，可以把 jc[m] 和 jc[n-m] 乘起来再放到pw里。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int mod=10007; int T,n,m,jc[mod+5],ans; int pw(int x,int k) { int ret=1;while(k){if(k&1)(ret*=x)%=mod;x=(ll)x*x%mod;k>>=1;}return ret; } void init() { jc[0]=1; for(int i=1;i<mod;i++)jc[i]=jc[i-1]*i%mod; } int C(int n,int m) { if(n<m)return 0;// return (ll)jc[n]*pw(jc[m]*jc[n-m],mod-2)%mod;//jc[m]*jc[n-m]一起求逆元 } int lucas(int n,int m) { if(!m)return 1; if(n<mod&&m<mod)return C(n,m); return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod; } int main() { init(); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); printf("%d\n",lucas(n,m)); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int mod=10007; ll n,m; int T,jc[mod+5],jcn[mod+5],ans; int pw(int x,int k) { int ret=1;while(k){if(k&1)(ret*=x)%=mod;(x*=x)%=mod;k>>=1;}return ret; } void init() { jc[0]=1; for(int i=1;i<mod;i++)jc[i]=jc[i-1]*i%mod; jcn[mod-1]=pw(jc[mod-1],mod-2); for(int i=mod-2;i>=0;i--)jcn[i]=jcn[i+1]*(i+1)%mod; } int C(int n,int m) { if(n<m)return 0;//// return jc[n]*jcn[m]%mod*jcn[n-m]%mod; } int lucas(ll n,ll m) { if(!m)return 1; if(n<mod&&m<mod)return C(n,m); return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod; } int main() { init(); scanf("%d",&T); while(T--) { scanf("%lld%lld",&n,&m); printf("%d\n",lucas(n,m)); } return 0; }
原文：https://www.cnblogs.com/Narh/p/9260759.html
