【盧卡斯定理】

1.要求：p 是質(zhì)數(shù)，m、n 很大但 p 很小 或者 n、m 不大但大于 p

2.定理內(nèi)容

• ?

其中，

3.推論

當(dāng)將 n 寫成 p 進(jìn)制：，將 m 寫成 p 進(jìn)制：?時(shí)，有：

4.實(shí)現(xiàn)

代碼實(shí)現(xiàn)可簡單理解為：

LL fac[N]; void getFac(){//構(gòu)造階乘fac[0]=1;for(int i=1;i<1000000;i++){fac[i]=fac[i-1]*i%MOD;} } LL quickPowMod(LL a,LL b,LL mod){//快速冪LL res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res; } LL getC(LL n,LL m,LL mod){//獲取C(n,m)%modif(m>n)return 0;return fac[n]*(quickPowMod(fac[m]*fac[n-m]%mod,mod-2,mod))%mod; } LL Lucas(LL n,LL m,LL mod){//盧卡斯定理if(m==0)return 1;return getc(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)%mod; } int main(){getFac();LL n,m;scanf("%lld%lld",&n,&m);printf("%lld\n",Lucas(n,k,MOD));return 0; }

【擴(kuò)展盧卡斯】

盧卡斯定理適用于 p 是素?cái)?shù)的情況，但當(dāng) p 不是素?cái)?shù)時(shí)，可以將其分解質(zhì)因數(shù)，將組合數(shù)按照盧卡斯定理的方法求 p 的質(zhì)因數(shù)的模，然后用中國剩余定理合并即可。

要求：p 不是質(zhì)數(shù) 且 m、n 很大但 p 很小 或者 n、m 不大但大于 p

例如：?

當(dāng)需要計(jì)算???時(shí)，可以求出：

然后對(duì)于方程組：，可以求出滿足條件的最小的 x，記為：

那么有：

但是，?并不是一個(gè)素?cái)?shù)，而是某個(gè)素?cái)?shù)的某次方，那么就需要計(jì)算??
對(duì)于?，已知?，因此若能計(jì)算出?，就能計(jì)算出??和?

設(shè)?，那么答案就是?，其中??代表計(jì)算 a 對(duì) b 的乘法逆元

于是，問題就轉(zhuǎn)換為如何計(jì)算?

例如：p=3，t=2，n=19，有：

n! = 1×2×3×4×5×6×7×8×…×19

? ? = (1×2×4×5×7×8×…×16×17×19) × (3×6×9×12×15×18)

? ? = (1×2×4×5×7×8×…×16×17×19) × 36 × (1×2×3×4×5×6)?

后半部分是 ，遞歸即可。前半部分是以??為周期的

下面是孤立的 19，可以知道孤立出來的長度不超過 ，直接計(jì)算即可。

對(duì)于最后剩下的 36，只要計(jì)算出 n!、m!、(n?m)! 里含有多少個(gè) p ，設(shè)他們分別有 x、y、z 個(gè) p，那么 x?y?z 就是?? 中 p 的個(gè)數(shù)，直接計(jì)算即可

LL powerMod(LL a,LL b,LL p) {//快速冪取模LL ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans; } LL fac(LL n,LL p,LL pk) {//計(jì)算階乘if(!n)return 1;LL ans=1;for(int i=1; i<pk; i++)if(i%p)ans=ans*i%pk;ans=powerMod(ans,n/pk,pk);for(int i=1;i<=n%pk;i++)if(i%p)ans=ans*i%pk;return ans*fac(n/p,p,pk)%pk; } LL extendGCD(LL a,LL b,LL &x,LL &y) {//擴(kuò)展歐幾里得if(!b){x=1;y=0;return a;}LL xx, yy;LL gcd=extendGCD(b,a%b,xx,yy);x=yy;y=xx-a/b*yy;return gcd; } LL inv(LL a,LL p){//計(jì)算逆元LL x,y;extendGCD(a,p,x,y);return (x%p+p)%p; } LL C(LL n,LL m,LL p,LL pk) {//組合數(shù)模質(zhì)數(shù)冪if(n<m)return 0;LL f1=fac(n,p,pk);LL f2=fac(m,p,pk);LL f3=fac(n-m,p,pk);LL cnt=0;for(LL i=n; i; i/=p)cnt+=i/p;for(LL i=m; i; i/=p)cnt-=i/p;for(LL i=n-m; i; i/=p)cnt-=i/p;return f1 * inv(f2,pk)%pk * inv(f3, pk)%pk * powerMod(p,cnt,pk)%pk; } LL a[N],c[N]; int tot; LL CRT() {//中國剩余定理LL M=1,ans=0;for (int i=0; i<tot; i++)M*=c[i];for (int i=0; i<tot; i++)ans=(ans + a[i] * (M/c[i])%M * inv(M/c[i],c[i])%M )%M;return ans; } LL extendLucas(LL n,LL m,LL p) {//擴(kuò)展盧卡斯for(int i=2; p>1&&i<=sqrt(p); i++) {LL temp=1;while(p%i==0) {p/=i;temp*=i;}if(temp>1) {a[tot]=C(n,m,i,temp);c[tot++]=temp;}}if(p>1) {a[tot]=C(n,m,p,p);c[tot++]=p;}return CRT(); } int main() {LL n,m,p;cin>>n>>m>>p;cout<<extendLucas(n,m,p);return 0; }

總結(jié)

以上是生活随笔為你收集整理的组合数学 —— 组合数取模 —— 卢卡斯定理与扩展卢卡斯定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。