首页 > 代码库 > [Lucas定理]【学习笔记】
[Lucas定理]【学习笔记】
这种神奇的东西...............
参考资料：http://www.cnblogs.com/jianglangcaijin/p/3446839.html
Lucas定理
适用于n很大p较小的时候
$ C_n^m\%p \ p \ is \ prime$
$ n=n_k*p^k+n_{k-1}*p^{k-1}+...+n_2*p^2+n_1*p+n_0 $
$ m=m_k*p^k+m_{k-1}*p^{k-1}+...+m_2*p^2+m_1*p+m_0 $
$ C_n^m=\prod\limits_{i=0}^k C_{n_i}^{m_i} $
证明见参考资料(我不会告诉你我没看的)
实现：这个形式很像多项式啊变量为p，n和m迭代/=p然后算C(n%p,m%p)就行了
ll Pow(ll a,ll b){ ll ans=1; for(;b;b>>=1,a=a*a%P) if(b&1) ans=ans*a%P; return ans;}ll Inv(ll a){return Pow(a,P-2);}ll C(ll n,ll m){ if(n<m) return 0; ll x=1,y=1; for(ll i=n-m+1;i<=n;i++) x=x*i%P; for(ll i=1;i<=m;i++) y=y*i%P; return x*Inv(y)%P;}ll Lucas(ll n,ll m){ if(n<m) return 0; ll re=1; for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P; return re;}
$ P \ is \ not \ prime $
看参考资料吧
$P$进行质因子分解，然后对于每个质因子$p_i^{e_i}$都得到一个同余方程
$x\equiv a_i\pmod {p_i^{e_i}}\\ $
用中国剩余定理合并就行了
但是$ C_n^m\%p_i^{e_i} $怎么求？
只要计算阶乘就行了，我们分成三部分：
比如：
$ n!=1∗2∗3∗4∗5∗6∗7∗8∗9∗10∗11∗12∗13∗14∗15∗16∗17∗18∗19 $
$ =(1∗2∗4∗5∗7∗8∗10∗11∗13∗14∗16∗17∗19)∗3^6∗(1∗2∗3∗4∗5∗6) $
假设当前质因子为$p$，$p_i^{e_i}=pr$
第一部分 $p$的倍数，有$\frac{n}{p}$个，提出$p$后形成了新的阶乘，递归解决
第二部分 提出的$p$ 只要最后计算$n!$中$p$出现次数然后 上-下 就行了
第三部分 不是$p$的倍数的部分；可以按$pr$分块，一共$\frac{n}{pr}$块，结果都是相同的；最后一块暴力计算即可
ll Pow(ll a,ll b,ll P){ ll ans=1; for(;b;b>>=1,a=a*a%P) if(b&1) ans=ans*a%P; return ans;}void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ if(b==0) d=a,x=1,y=0; else exgcd(b,a%b,d,y,x),y-=(a/b)*x;}ll Inv(ll a,ll n){ ll d,x,y; exgcd(a,n,d,x,y); return d==1?(x+n)%n:-1;}ll Fac(ll n,ll p,ll pr){ if(n==0) return 1; ll re=1; for(ll i=2;i<=pr;i++) if(i%p) re=re*i%pr; re=Pow(re,n/pr,pr); ll r=n%pr; for(int i=2;i<=r;i++) if(i%p) re=re*i%pr; return re*Fac(n/p,p,pr)%pr;}ll C(ll n,ll m,ll p,ll pr){ if(n<m) return 0; ll x=Fac(n,p,pr),y=Fac(m,p,pr),z=Fac(n-m,p,pr); ll c=0; for(ll i=n;i;i/=p) c+=i/p; for(ll i=m;i;i/=p) c-=i/p; for(ll i=n-m;i;i/=p) c-=i/p; ll a=x*Inv(y,pr)%pr*Inv(z,pr)%pr*Pow(p,c,pr)%pr; return a*(MOD/pr)%MOD*Inv(MOD/pr,pr)%MOD;}ll Lucas(ll n,ll m){ ll x=MOD,re=0; for(ll i=2;i<=MOD;i++) if(x%i==0){ ll pr=1; while(x%i==0) x/=i,pr*=i; re=(re+C(n,m,i,pr))%MOD; } return re;}
[Lucas定理]【学习笔记】