lucas

· · 题解

卢卡斯定理

首先我们需要证明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

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