【扩展lucas定理】

短命女 2021-12-03 07:53 299阅读 0赞

洛谷模板题面：[https://www.luogu.org/problemnew/show/P4720][https_www.luogu.org_problemnew_show_P4720]

扩展卢卡斯被用于解决模数为合数情形下的组合数问题。  
首先我们把模数mod质因数分解，解决模每个素数的幂意义下的组合数这样一个子问题，最后用crt把他们合并到一起。  
那么我们现在要解决这样一个问题：  
\\\[ C(n,m) \\quad mod \\quad p^k \\\]  
其中p为质数。  
\$p^k\$可能很大，而且性质与p不同，使用单纯的lucas解决肯定是不行了。  
我们考虑把组合数拆成阶乘的形式，发现 $n! ,m! , (n-m)! $都有可能含有质数p，而当分母含有p的时候与模数不互质，逆元是没有办法求的，所以我们必须把p全都提出。  
化成这种形式：  
\\\[ \\frac\{\\frac\{n!\}\{p^a\}\}\{\\frac\{m!\*(n-m)!\}\{p^b\}\}\*p^\{(a-b)\} \\\]  
发现 去除掉所有p的\$n!\$ 是有非常美妙的性质的，它可以提出一段可求长度的去p阶乘，然后剩下一部分是更小规模的阶乘（读者可以试着导一导），有了这个性质，我们便可以递归求解了。预处理出来一些东西后，可以像普通lucas一样简洁，高效。

细节部分详见代码中分解质因数时的预处理部分和Fac函数。

## 注意： ##

1、这里求逆元要用exgcd。

2、复杂度与min(n,max\_p)有关，当mod比较大n较小时别忘了取min。

接下来是一份AC代码：

#include<bits/stdc++.h> using namespace std; const int N =1000005; #define rep(i,a,b) for(register int i=(a);i<=(b);++i) typedef long long ll; ll m,n; int mod; ll fac[N],inv[N]; ll ksm(ll x,ll y,ll M){ ll aa=1ll; for(x%=M;y;y>>=1,x=(x*x)%M)if(y&1)aa=(aa*x)%M; return aa; } int p[N],pk[N],cnt; ll sum,fak[22][N]; ll exgcd(ll x,ll y,ll &a,ll &b){ if(!y){a=1,b=0;return x;} ll d=exgcd(y,x%y,b,a); b-=x/y*a; return d; } inline ll Inv(ll x,ll y){ ll inv,rua; exgcd(x,y,inv,rua); return (inv+y)%y; } ll Fac(ll x,int i){ if(x==0||x==1)return 1; return Fac(x/p[i],i)*ksm(fak[i][pk[i]-1],x/pk[i],pk[i])%pk[i]*fak[i][x%pk[i]]%pk[i]; } ll ex_Lucas(ll x,ll y,int i){ if(x<y)return 0; ll num=0; for(ll j=x;j;j/=p[i]) num+=j/p[i]; for(ll j=y;j;j/=p[i])num-=j/p[i]; for(ll j=x-y;j;j/=p[i])num-=j/p[i]; return Fac(x,i)*Inv(Fac(y,i),pk[i])%pk[i]*Inv(Fac(x-y,i),pk[i])*ksm(p[i],num,pk[i])%pk[i]; } ll ans; int main(){ scanf("%lld%lld%d",&n,&m,&mod); int x=mod; for(int i=2;i*i<=mod;++i){ if(x%i==0){ p[++cnt]=i; pk[cnt]=1; while(x%i==0)x/=i,pk[cnt]*=i; sum=1;fak[cnt][0]=1; rep(j,1,pk[cnt]-1){ if(j%p[cnt])sum=sum*j%pk[cnt]; fak[cnt][j]=sum; } } } if(x!=1){ ++cnt,p[cnt]=pk[cnt]=x; sum=1;fak[cnt][0]=1; rep(j,1,pk[cnt]-1){ if(j%p[cnt])sum=sum*j%pk[cnt]; fak[cnt][j]=sum; } } ll tmp; rep(i,1,cnt){ tmp=ex_Lucas(n,m,i); ans=(ans+tmp*(mod/pk[i])%mod*Inv(mod/pk[i],pk[i])%mod)%mod; } printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/Sinuok/p/11129587.html

[https_www.luogu.org_problemnew_show_P4720]: https://www.luogu.org/problemnew/show/P4720