自动搬运

查看原文

来自洛谷，原作者为

	Lance1ot Panzer Vor！

搬运于2025-08-24 21:52:56，当前版本为作者最后更新于2018-07-05 17:30:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

卢卡斯定理

首先我们需要证明$C_p^i\equiv\frac{p}{i}C_{p-1}^{i-1}\equiv 0~~~(mod~p),(1<=i<=p-1)$

$C_p^i=\frac{p!}{i!(p-i)!}=\frac{p}{i} \frac{(p-1)!}{(i-1)!(p-1-i+1)!} \frac{p}{i} \frac{(p-1)!}{(i-1)!(p-i)!}=\frac{p}{i}C_{p-1}^{i-1}$

得证。

然后根据这种性质和二项式定理。，我们马上得出

$(1+x)^p\equiv C_p^0+C_p^1x^{1}+....+C_p^px^p\equiv C_p^0x^0+C_p^px^p\equiv 1+x^p(mod ~p)$

然后我们接下来要求证，这个式子是我们递归时用到的。

$C_a^b\equiv C_{a_0}^{b_0}\cdot C_{a_1p}^{b_1p} \cdot C_{a_2p^2}^{b_2p^2}.....(mod~p)$

但其实我们令$a=lp+r,b=sp+j$随便起的

求证$C_a^b\equiv C_{l}^{s}\cdot C_{r}^{j}(mod~p)$然后利用性质递归求解就可以了。

继续从二次项定理出发

$(1+x)^a=(1+x)^{lp} \cdot (1+x)^r$

然后展开$(1+x)^{lp}$

$(1+x)^{lp} \equiv ((1+x)^p)^l \equiv (1+x^p)^l(mod~p)$

$\therefore (1+x)^a \equiv (1+x^p)^l \cdot (1+x)^r(mod~p)$

观察项$x^b$的系数

$\because C_a^bx^b \equiv C_l^sx^{sp} \cdot C_r^jx^j(mod~p)$

$\therefore C_a^bx^b \equiv C_l^s \cdot C_r^jx^b(mod~p)$

$\therefore C_a^b\equiv C_l^s\cdot C_r^j \equiv C_{\lfloor \frac{a}{p} \rfloor}^{\lfloor \frac{b}{p} \rfloor}\cdot C_{a~mod~p}^{b~mod~p}(mod~p)$

Ps:左边的是原来不经过化简的二项式展开，同时因为保证了$a=lp+r,b=sp+j$,所以右边不会出现其他的项。

后：本人已退役qwq。而且并没有用上自己学的（自我感觉省选无望qwq）

而且也系统的学过了二项式（好像暴漏年龄了）

对之前的错误表示抱歉，也欢迎大家继续挑刺/cy

转载什么的就不用问。转~，都可以转~