卢卡斯定理

问题求解\(C_{n+m}^m \pmod{p}\)的值

当然可以不用卢卡斯定理。

\[C_{n+m}^m=\frac{(n+m)!}{n!*m!} \]

\(\color{Orange}{问题似乎很简单，分子暴力乘，分母同理求个逆元ok了。}\)

\(\color{Green}{错错错!!!}\)

\(当分母含有x个p因子，分子含有y个p因子。\)

\(\color{Blue}{若x==y,那么显然C_{n+m}^m \pmod{p}不为0}\)

\(\color{Purple}{但我们是分别对分子分母计算求余的,一遇到含p因子时就被模成0了}\)

\(\color{#000}{正确的做法是每次都除去p因子，并且统计因子个数}\)

\(分子分母p因子个数相同，算出的答案就是答案。不同，答案就是0.\)

我的代码

当然也可以用卢卡斯定理。

但是因为我还没看懂的原因，先留坑....

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100009],n,m,p;
ll qpow(ll a,ll n)
{
	ll ans=1;
	while(n)
	{
		if(n&1)	ans=ans*a%p;
		n>>=1;
		a=a*a%p;
	}
	return ans;
}
ll C(ll n,ll m)
{
	if(m>n)	return 0;
	return a[n]*qpow(a[m],p-2)%p*qpow(a[n-m],p-2)%p;
}
ll Lucas(ll n,ll m)
{
	if(!m)	return 1;
	return C(n%p,m%p)*(Lucas(n/p,m/p))%p;	
} 
int main()
{
	cin>>n>>m>>p;
	a[0]=1;
	for(ll i=1;i<=p;i++)	a[i]=(a[i-1]*i)%p;
	cout<<Lucas(n+m,n)<<endl;
}

卢卡斯定理

原文：https://www.cnblogs.com/iss-ue/p/12744810.html