本文主要是介绍Vision_MATH_Lucas定理及扩展，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
///定义：/*
Lucas定理：
（1）求解C(n,m)%p, n和m是非负整数，p是质数.
（2）结论1. Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p);
（3）结论2. 把n写成p进制a[n]a[n-1]a[n-2]...a[0]，把m写成p进制b[n]b[n-1]b[n-2]...b[0]，
则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余。
（4）注：n,m不能大于10^5，不大于情况下用逆元的方法可以解决，如果大了就不能解决。
*/
///代码：
/*
**name:Lucas定理
**function:求解组合数取模C(n,m)%p,(p素数)
**输入参数：n,m,p
**输出参数：C(n,m)%p
*/
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;///求逆元
LL exp_mod(LL a, LL b, LL p) {LL res = 1;while(b != 0) {if(b&1) res = (res * a) % p;a = (a*a) % p;b >>= 1;}return res;
}
LL Comb(LL a, LL b, LL p) {if(a < b) return 0;if(a == b) return 1;if(b > a - b) b = a - b;LL ans = 1, ca = 1, cb = 1;for(LL i = 0; i < b; ++i) {ca = (ca * (a - i))%p;cb = (cb * (b - i))%p;}ans = (ca*exp_mod(cb, p - 2, p)) % p;return ans;
}LL Lucas(int n, int m, int p) {LL ans = 1;while(n&&m&&ans) {ans = (ans*Comb(n%p, m%p, p)) % p;n /= p;m /= p;}return ans;
}int main() {Read();int n, m, p;while(~scanf("%d%d%d", &n, &m, &p)) {printf("%lld\n", Lucas(n, m, p));}return 0;
}
/*
**name:Lucas定理扩展
**function:求解组合数取模C(n,m)%p,(p为任意数)
**输入参数：n,m,p
**输出参数：C(n,m)%p
*/
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,m,MOD,ans;LL fast_pow(LL a,LL p,LL Mod){LL ans=1LL;for (;p;p>>=1,a=a*a%Mod)if (p&1)ans=ans*a%Mod;return ans;
}
void exgcd(LL a,LL b,LL &x,LL &y){if (!b) x=1LL,y=0LL;else exgcd(b,a%b,y,x),y-=a/b*x;
}
LL inv(LL A,LL Mod){if (!A) return 0LL;LL a=A,b=Mod,x=0LL,y=0LL;exgcd(a,b,x,y);x=((x%b)+b)%b;if (!x) x+=b;return x;
}
LL Mul(LL n,LL pi,LL pk){if (!n) return 1LL;LL ans=1LL;if (n/pk){for (LL i=2;i<=pk;++i)if (i%pi) ans=ans*i%pk;ans=fast_pow(ans,n/pk,pk);}for (LL i=2;i<=n%pk;++i)if (i%pi) ans=ans*i%pk;return ans*Mul(n/pi,pi,pk)%pk;
}
LL C(LL n,LL m,LL Mod,LL pi,LL pk){if (m>n) return 0LL;LL a=Mul(n,pi,pk),b=Mul(m,pi,pk),c=Mul(n-m,pi,pk);LL k=0LL,ans;for (LL i=n;i;i/=pi) k+=i/pi;for (LL i=m;i;i/=pi) k-=i/pi;for (LL i=n-m;i;i/=pi) k-=i/pi;ans=a*inv(b,pk)%pk*inv(c,pk)%pk*fast_pow(pi,k,pk)%pk;return ans*(Mod/pk)%Mod*inv(Mod/pk,pk)%Mod;
}
int main(){scanf("%I64d%I64d%I64d",&n,&m,&MOD);for (LL x=MOD,i=2;i<=MOD;++i)if (x%i==0){LL pk=1LL;while (x%i==0) pk*=i,x/=i;ans=(ans+C(n,m,MOD,i,pk))%MOD;}printf("%I64d\n",ans);
}
///扩展：
/*
（1）组合数的递推公式
C(n,m) = C(n-1,m)+C(n,m-1);
C(n,k) = (n-k+1)/k*C(n,k-1) , C(n,0) = 1;
（2）判断C(n,m)的奇偶性：
if(n&m==m)C(n,m)为奇数
else C(n,m)为偶数
*/
这篇关于Vision_MATH_Lucas定理及扩展的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
