组合数取模(Lucas 定理 & exLucas 定理)学习笔记

需要n,mlimn,m\le lim 的一些 CnmC_n^mpp 的结果,但是递推预处理组合数时间复杂度无法接受时,该怎么办呢?

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(1) 的,预处理时间复杂度则是 O(lim)O(lim)

1x0 特殊手段

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

1x1 limplim\ge p,但 pp 是质数的情况(Lucas)

limplim\ge p 时,所有 ipi\ge pi!i! 都不与 pp 互质,没有模 pp 意义下的逆元,普通方法就行不通了。

这时可以借助 Lucas 定理:

CnmCnmodpmmodpCnpmp(modp)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(logpm)O(\log_p m) 的,预处理时间复杂度则是 O(min(lim,p))O(\min(lim,p))


定理证明:

【引理 1】 对于任意一个满足 1x<p1\le x<p 的正整数 xx,均有 Cpx0(modp)C_p^x\equiv0\pmod p,证明如下:

Cpxp!x!(px)!(modp)p(p1)!x!(px)!(modp)0(modp)\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)pap+bp(modp)(a+b)^p\equiv a^p+b^p\pmod p,证明如下:

根据二项式定理:

(a+b)pi=0pCpiaibpi(modp)ap+bp+i=1p1Cpiaibpi(modp)ap+bp(modp)(由引理 1 得)\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 定理)】 CnmCnmodpmmodpCnpmp(modp)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,证明如下:

xx 为一个满足 1x<p1\le x<p 的正整数,由二项式定理得:(1+x)ni=0nCnixi(1+x)^n\equiv \sum\limits_{i=0}^n C_n^ix^i

pn=np,pm=mp,rn=nmodp,rm=mmodpp_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,那么有:

(1+x)n(1+x)ppn+rn(modp)[(1+x)p]pn(1+x)rn(modp)(1+xp)pn(1+x)rn(modp)i=0pnj=0rnCpniCrnjxip+j(modp)(根据二项式定理)i=0nCpnipCrnimodpxi(modp)\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}

所以:

i=0nCnixii=0nCpnipCrnimodpxi(modp)\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

CnmCpnpmCrnrm(modp)C_n^m\equiv C_{p_n}^{p_m}\cdot C_{r_n}^{r_m}\pmod p

证毕。


练习:P3773 [CTSC2017]吉夫特

1x2 pp 不是质数的情况(exLucas)

未完待续。