跳到主要内容

排列组合

概述

围绕从 n 个不同元素中取出 m 个的方案数展开：组合数 C(n,m) 不计顺序，排列数 A(n,m) 计顺序，两者都可由阶乘表出。预处理阶乘与阶乘逆元后，每次求组合数或排列数都是 O(1)，其中逆元借助线性递推一次性求出全部，避免逐个求逆。当模数 p 为质数、而 n 与 m 很大以致无法直接预处理阶乘时，用卢卡斯定理把 n、m 放到 p 进制下逐位取组合数再相乘、递归求解，从而在合理复杂度内算出 C(n,m) 模 p。文中给出线性逆元、组合数、排列数与卢卡斯定理的完整代码。

参考资料​

线性逆元​

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

详见 模逆元。

181 Bcpp
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;
	}
}

组合​

组合数 CnmC_n^m（即 (nm)\binom{n}{m}）表示从 nn 个不同元素中取出 mm 个、不计顺序的方案数。预处理阶乘与阶乘逆元后可 O(1)O(1) 求值。

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

排列​

排列数 AnmA_n^m 表示从 nn 个不同元素中取出 mm 个、按顺序排列的方案数。

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

卢卡斯定理​

卢卡斯定理（Lucas）用于质数模 pp 下、nn 与 mm 很大时求 (nm) mod p\binom{n}{m}\bmod p：把 nn、mm 在 pp 进制下逐位取组合数再相乘，递归求解。

Cnm≡Cn/pm/p⋅Cn mod pm mod p(modp)C_n^m\equiv C_{n/p}^{m/p}\cdot C_{n\bmod p}^{m\bmod p}\pmod p
89 Bcpp
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 为质数。