组合数取模（Lucas 定理 & exLucas 定理）学习笔记

需要求 $n,m\le lim$ 的一些 $C_n^m$ 模 $p$ 的结果，但是递推预处理组合数时间复杂度无法接受时，该怎么办呢？

0x0 普通方法

最基础的方法是预处理出阶乘和阶乘的逆元，直接套公式计算：

inline void init()
{
	fra[0]=1;
	for(int i=1;i<=lim;i++)
	{
		fra[i]=1ll*fra[i-1]*i%p;
	}
	inv[lim]=qpow(fra[lim],p-2);
	for(int i=lim;i>=1;i--)
	{
		inv[i-1]=1ll*inv[i]*i%p;
	}
}

inline int C(int n,int m)
{
	return n<m?0:1ll*fra[n]*fra[n-m]%p*fra[m]%p;
}

这样做的话单次时间复杂度是 $O(1)$ 的，预处理时间复杂度则是 $O(lim)$。

1x0 特殊手段

普通方法已经能满足大多数情况，但是有两种特殊情况除外。

1x1 $lim\ge p$，但 $p$ 是质数的情况（Lucas）

当 $lim\ge p$ 时，所有 $i\ge p$ 的 $i!$ 都不与 $p$ 互质，没有模 $p$ 意义下的逆元，普通方法就行不通了。

这时可以借助 Lucas 定理：

$C_n^m\equiv C_{n\operatorname{mod}p}^{m\operatorname{mod} p}\cdot C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}\pmod p$

来实现递归求解：

inline void init()
{
	int lim2=min(lim,p-1);
	fra[0]=1;
	for(int i=1;i<=lim2;i++)
	{
		fra[i]=1ll*fra[i-1]*i%p;
	}
	inv[lim2]=qpow(fra[lim2],p-2);
	for(int i=lim2;i>=1;i--)
	{
		inv[i-1]=1ll*inv[i]*i%p;
	}
}
inline int C(int n,int m)
{
	return n<m?0:1ll*fra[n]*inv[m]%p*inv[n-m]%p;
}

int lucas(int n,int m)
{
	return m==0?1:1ll*C(n%p,m%p)*lucas(n/p,m/p)%p;
}

这样做的话单次时间复杂度是 $O(\log_p m)$ 的，预处理时间复杂度则是 $O(\min(lim,p))$。

定理证明：

【引理 1】 对于任意一个满足 $1\le x<p$ 的正整数 $x$，均有 $C_p^x\equiv0\pmod p$，证明如下：

$\begin{aligned}C_p^x&\equiv\dfrac{p!}{x!(p-x)!}\pmod p\\&\equiv p\cdot\dfrac{(p-1)!}{x!(p-x)!}\pmod p\\&\equiv 0\pmod p\end{aligned}$

【引理 2】 $(a+b)^p\equiv a^p+b^p\pmod p$，证明如下：

根据二项式定理：

$\begin{aligned}(a+b)^p&\equiv\sum\limits_{i=0}^pC_p^i\cdot a^i\cdot b^{p-i}\pmod p\\&\equiv a^p+b^p+\sum\limits_{i=1}^{p-1}C_p^i\cdot a^i\cdot b^{p-i}\pmod p\\&\equiv a^p+b^p\pmod p\text{（由引理 1 得）}\end{aligned}$

【定理 1（Lucas 定理）】 $C_n^m\equiv C_{n\operatorname{mod}p}^{m\operatorname{mod} p}\cdot C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}\pmod p$，证明如下：

设 $x$ 为一个满足 $1\le x<p$ 的正整数，由二项式定理得：$(1+x)^n\equiv \sum\limits_{i=0}^n C_n^ix^i$。

令 $p_n=\lfloor\frac{n}{p}\rfloor,p_m=\lfloor\frac{m}{p}\rfloor,r_n=n\operatorname{mod}p,r_m=m\operatorname{mod} p$，那么有：

$\begin{aligned}(1+x)^n&\equiv (1+x)^{p\cdot p_n+r_n}\pmod p\\&\equiv [(1+x)^p]^{p_n}\cdot(1+x)^{r_n}\pmod p\\&\equiv (1+x^p)^{p_n}\cdot (1+x)^{r_n}\pmod p\\&\equiv \sum\limits_{i=0}^{p_n}\sum\limits_{j=0}^{r_n}C_{p_n}^i\cdot C_{r_n}^j\cdot x^{ip+j}\pmod p\text{（根据二项式定理）}\\&\equiv\sum\limits_{i=0}^nC_{p_n}^{\lfloor\frac{i}{p}\rfloor}\cdot C_{r_n}^{i\operatorname{mod} p}\cdot x^i\pmod p\end{aligned}$

所以：

$\sum\limits_{i=0}^n C_n^ix^i\equiv\sum\limits_{i=0}^nC_{p_n}^{\lfloor\frac{i}{p}\rfloor}\cdot C_{r_n}^{i\operatorname{mod} p}\cdot x^i\pmod p$

$C_n^m\equiv C_{p_n}^{p_m}\cdot C_{r_n}^{r_m}\pmod p$

证毕。

练习：P3773 [CTSC2017]吉夫特

1x2 $p$ 不是质数的情况（exLucas）

未完待续。