Skip to main content

排列组合

参考资料​

线性逆元​

i−1≡−⌊pi⌋(p mod i)−1(modp)i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor(p\bmod i)^{-1}\pmod p

详见 模逆元。

ll inv[N],fac[N],jv[N];
void init()
{
	fac[0]=jv[0]=1;
	for(int i=1;i<N;i++)
	{
		inv[i]=i==1?1:(mod-mod/i)*inv[mod%i]%mod;
		fac[i]=fac[i-1]*i%mod;
		jv[i]=jv[i-1]*inv[i]%mod;
	}
}

组合​

Cnm=n!m!(n−m)!C_{n}^{m}=\frac{n!}{m!(n-m)!} 
ll C(ll n,ll m)
{
	if(n<m||m<0)return 0;
	return fac[n]*jv[n-m]%mod*jv[m]%mod;
}

排列​

Anm=n!(n−m)!A_{n}^{m}=\frac{n!}{(n-m)!} 
ll A(ll n,ll m)
{
	if(n<m||m<0)return 0;
	return fac[n]*jv[n-m]%mod;
}

卢卡斯定理​

Cnm=Cm/pn/p⋅Cm mod pn mod p(modp)C_{n}^{m}=C_{m/p}^{n/p}\cdot C_{m\bmod p}^{n\bmod p}\pmod p 
ll lucas(ll n,ll m)
{
	if(m==0)return 1;
	return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}

例题​

洛谷 P3807 【模板】卢卡斯定理/Lucas 定理

给定整数 n,m,pn, m, p 的值，求出 Cn+mn mod pC_{n + m}^n \bmod p 的值。

输入数据保证 pp 为质数。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
int mod;
ll inv[N],fac[N],jv[N];
void init()
{
	fac[0]=jv[0]=1;
	for(int i=1;i<N;i++)
	{
		inv[i]=i==1?1:(mod-mod/i)*inv[mod%i]%mod;
		fac[i]=fac[i-1]*i%mod;
		jv[i]=jv[i-1]*inv[i]%mod;
	}
}
ll C(ll n,ll m)
{
	if(n<m||m<0)return 0;
	return fac[n]*jv[n-m]%mod*jv[m]%mod;
}
ll lucas(ll n,ll m)
{
	if(m==0)return 1;
	return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m>>mod;
		init();
		cout<<lucas(n+m,n)<<'\n';
	}
	return 0;
}