拓展卢卡斯定理

相关知识

线性同余方程组

定理

时间复杂度 O(p logn)

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;

ll ExGcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	ll ans=ExGcd(b,a%b,x,y);
	ll t=y;
	y=x-(a/b)*y;
	x=t;
	return ans;
}
inline ll ksc(ull x,ull y,ll p)
{
	return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
ll fastPow(ll a,ll b,ll p)
{
	ll res=1;
	a%=p;
	while(b)
	{
		if(b&1) res=ksc(res,a,p);
		a=ksc(a,a,p);
		b>>=1;
	}
	return res;
}
ll inv(ll a,ll p)//无解返回 -1
{
	ll x,y;
	if(ExGcd(a,p,x,y)!=1) return -1;
	return (x%p+p)%p;//正数化
}
ll crt(ll N, ll m,ll p)
{
	return ksc(N*(p/m),inv(p/m, m),p);
}

ll fac(ll n, ll p, ll k) 		//k = p^x
{
	if(!n) return 1;
	ll ans = 1;
	for(ll i = 2; i <= k; i++)
	{
		if(i%p) ans = ans*i % k;
	}
	ans = fastPow(ans, n/k, k);
	for(ll i = 2; i <= n%k; i++)
	{
		if(i%p) ans = ans*i % k;
	}
	return ans*fac(n/p, p, k)%k;
}

ll C(ll n, ll m, ll p, ll k) 	//k = p^x
{
	if(n < m) return 0;
	ll a = fac(n,p,k), b = fac(m,p,k), c = fac(n-m,p,k);
	ll cnt = 0;
	for(ll i = p; i <= n; i *= p) cnt += n/i;
	for(ll i = p; i <= m; i *= p) cnt -= m/i;
	for(ll i = p; i <= n-m; i *= p) cnt -= (n-m)/i;
	return a*inv(b, k)%k * inv(c, k)%k * fastPow(p, cnt, k)%k;
}

ll exlucas(ll n,ll m,ll p)
{
	ll t = p, ans = 0;
	for(ll i = 2; i*i <= t; i++)
	{
		if(t%i) continue;
		ll tmp = 1;
		while(t%i == 0)
		{
			tmp *= i;
			t /= i;
		}
		ans = (ans+crt(C(n, m, i, tmp), tmp,p))%p;
	}
	if(t > 1) ans = (ans+crt(C(n, m, t, t), t,p))%p;
	return ans%p;
}

int main()
{
	ll n,m,p;
	cin >> n >> m >> p;
	cout << exlucas(n,m,p) << endl;

	return 0;
}