Lucas 定理 及扩展Lucas 学习笔记
Lucas 定理：
解决问题：
求
,(p)是质数。
内容：
证明：
因为wyh很懒为方便写作，以下的 = 都是mod p 意义下的同余,/都是整除（即向下取整）
对于任意质数(p)，有
由费马小定理得：
设：
即：
现在推一波柿子：
前方高能！这里有一种很巧妙的想法反正wyh认为自己的智商是想不到的qwq：考虑这个等式两边(m^x)的系数
等式左边：
等式右边：
所以：
Code
inline ll C(ll n,ll m)
{
if(n<m) return 0;
m=min(m,n-m);
ll x1=1,x2=1;
for(int i=n-m+1;i<=n;++i) x1=x1*i%p;
for(int i=1;i<=m;++i) x2=x2*i%p;
return x1*inv(x2)%p;
}
inline ll lucas(ll n,ll m)
{
if(!m) return 1;
return C(n%p,m%p)*lucas(n/p,m/p)%p;
}
扩展Lucas：
和Lucas定理也没有啥关系
解决问题：
求
,(p)不一定是质数。
内容：
其中(a_i)表示(C_n^mmod p_i^{k^i})
求法：
主要是如何求(a_i)，即如何求(n!mod p^c)。
证明：
证明
由于同余方程在模(p={p_1}^{k_1}*{p_2}^{k_2}*…*{p_q}^{k_q})的意义下有唯一解(具体的证明见中国剩余定理)，可以证明答案的正确性。
由于(p={p_1}^{k_1}*{p_2}^{k_2}*…*{p_q}^{k_q})实际上是一个质因数分解，所以对于(forall p_i^{k_i})都是互质的，我们就可以直接用中国剩余定理合并。
所以现在主要的问题就是怎么求(C_m^nmod {p_i}^{k_i})。
考虑最暴力的方法(C_m^n={n!over m!(n-m)!})。我们就必须求出(n!\% {p_i}^{k_i},m!\% {p_i}^{k_i},(n-m)!\% {p_i}^{k_i})。
于是我们就要考虑怎么求出(n!\% {p_i}^{k_i})
我们发现，求解(n!)可以分为3部分：
第一部分是(p_i)的幂的部分，也就是(3^7)即(p_i^{n/p_i})，可以直接求解；
第二部分是一个新的阶乘，也就是(7!)即(n/p_i!)，可以递归下去求解；
第三部分是除前两部分之外剩下的数
我们再考虑一下第三部分是什么
我们可以把它分段，每(p_i^{k_i})个数分一段，当然其中要剔除(p_i)的倍数。这样就会发现一个非常有趣的性质：
但是还剩下一些孤立的数，可以发现剩下孤立的数长度不会超过({p_i}^{k_i})，（wyh也不知道是怎么发现的qwq）所以就可以愉快的暴力了。
现在还有最后一个问题，我们把(m!\%{p_i}^{k_i},(n-m)!\%{p_i}^{k_i})拆完以后，有可能与({p_i}^{k_i})不是互质的。这样就不能直接求逆元了。
所以要将(m!\%{p_i}^{k_i},(n-m)!\%{p_i}^{k_i})中质因子(p_i)先全部除去，求出逆元后再全部乘回去。。。
计算(n!)中质因子(p_i)的个数(x)的公式为(x=lfloor{nover p_i} floor+lfloor{nover p_i^2} floor+lfloor{nover p_i^3} floor+…)
递推式可写为(f(n)=f(lfloor{nover p_i} floor)+lfloor{nover p_i} floor)
我们就可以再考虑一下第一部分，其实就不需要求了，因为它都是(p_i)的倍数。
扩展 Lucas ：
给泥萌讲个真实的故事：
真实的我：
暑假，我打算学数学。
前天下午，知道我打完几道lucas定理的裸题之前，一切正常。然后，手贱的我反手点开了一道“扩展Lucas”，从此踏上了不归路。昨天自闭了一天，最终放弃了学扩卢，决定找一些“接地气”的题做做，于是我开始做近3年的NOIP题。于是我打开NOIP2016Day1。T1：玩具谜题。A掉。T2：天天爱跑步。T3：换教室。。于是自闭到现在。。。