$ C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p}*C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p $
一句话概括，就是一个组合数可以拆成\(P\)进制下的乘积
这个算法可以处理当\(m,n\)非常大的时候的取模\((\)当然你可以用高精度处理\()\)
\(Lucas(x,0,mod)=1\)，直接返回\(1\)即可
注意处理阶乘的数组 \(a[0]=1\)，因为\(0!=1\)
开\(long~long\)
注意处处取模
给定\(n,m,p(1<=n,m,p<=10^5)\)
求\(C_{n+m}^m\ mod\ p\)
保证\(p\)为质数
第一行一个数\(T(T<=10)\)，表示数据组数
第二行开始共\(T\)行，每行三个数\(n,m,p\)
共\(T\)行,每行一个整数表示答案
就是模板，我又有什么可说的呢
用\(a[i]\)表示\(i\)的阶乘，当然要取模 有个特别注意的点，当且仅当\(gcd(a,p)=1\)且\(p\)是质数时，\(a^{p-1}=1\pmod p\)(费马小定理)成立，所以这个题直接用费马小定理处理逆元即可 具体细节自己看代码吧
#include<cstdio> #include<iostream> #define maxn 100010 #define ll long long using namespace std; ll a[maxn]; int T,n,m,p; ll quickpower(ll A,int B,int mod) { A%=mod; ll ans=1; while(B) { if(B&1) ans=(ans*A)%mod; A=(A*A)%mod; B>>=1; } return ans%mod; } inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll CC(ll n,ll m) { /*注意判断*/if(m>n) return 0; //注意取模 //费马小定理求逆元 return ((a[n]*quickpower(a[m],p-2,p))%p*quickpower(a[n-m],p-2,p)%p); } ll Lucas(ll n,ll m) { if(!m) return 1; return CC(n%p,m%p)*Lucas(n/p,m/p)%p;//注意取模 } int main() { T=read(); while(T--) { n=read(); m=read(); p=read(); a[0]=1;//特别注意!!! for(int i=1;i<=p;++i) a[i]=(a[i-1]*i)%p; printf("%d\n",Lucas(n+m,m)); } return 0; }转载于:https://www.cnblogs.com/Liuz8848/p/11019347.html
相关资源：JAVA上百实例源码以及开源项目