Lucas定理理解

xiaoxiao2021-02-28  83

Lucas定理:C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p (p为素数) 结论十分简单加好记,但是这里还是给出下证明 可以认为是从百度百科上摘的,但是有我自己的理解 顺便补充一句,百度百科是坑爹的 易知:C(p,f)=p!/(p-f)!*f! => C(p,f)≡0(mod p)其中0<f<p 关于这一步我当年有一个证法: C(p,f)=p(p-1)……(p-f+1)/f! 两个连续的整数之间必有1个被2整除 三个连续的整数之间必有1个被3整除 ……(以此类推) 那么因为p为质数,f<p 所以 2~f中无任何数整除p 根据组合数定义f!一定整除p(p-1)……(p-f+1) (这步有点强行啊,但组合数确实不可能是分数了)  综上:f!|(p-1)(p-2)……(p-f+1) 令n=sp+q,m=tp+r (1+x)^n≡(1+x)^(sp+q)≡((1+x)^sp*(1+x)^q ≡(1+x^p)^(s)*(1+x)^q (mod p) 最后一步有点难理解 化简一下:即是证 (1+x)^ps≡(1+x^p)^s (mod p) 好,我们第一行的东西有用了 C(p,f)≡0(mod p) 0<f<p 根据二项式定理 那么(1+x)^p除了首位两项也就是1和x^p外都可以被p给除掉 就证明出来了 然后再来一次可爱的二项式定理: (1+x^p)^(s)*(1+x)^q=∑(C(s,i)*x^(i*p))*∑(C(q,j)*x^j) <i from 0 to s> <j from 0 to q> 于是得到: (1+x)^(sq+p)≡∑(C(s,i)*x^(i*p))*∑(C(q,j)*x^j) <i from 0 to s> <j from 0 to q> 那么左边x^(tp+r)的系数为C(sp+q,tp+r) 通过观察,那么当且仅当 i=t,j=r ,能够得到x^(tp+r) 的系数 即:C(s,t)*C(q,r)≡C(sp+q,tp+r) (mod p) (这个怎么观察的还没搞懂,懂了的大佬们给我说一声) 即证 最后给出一个Lucas的版 LL Lucas(LL n,LL k){     if(!k) return 1;     else         return C(n%mod,k%mod)*Lucas(n/mod,k/mod)%mod; } 接上的那个题 hdu3944 DP? 给出n,k,p,求在杨辉三角中从C(0,0)到C(n,k)所经过的数之和最小 输出这个数mod p,其中k,n小于10的9次方,p小于10000   这道题要是用dp来做,不知道会炸到哪里去了,正解是Lucas定理 首先,你得知道从C(n,k)到C(0,0)(如果k在n/2的右边,则k=n-k), 最短的路径一定是先沿着C(i,0)这段路走,然后再在某个地方斜向下 刚好走到C(n,m)   然后我们就可以得到这样一个表达式 ans=c(n-k,0)+c(n-k+1,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k =c(n-k+1,0)+c(n-k+1,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k =c(n-k+2,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k =c(n-k+3,2)+...+c(n-k+i,i)+...+c(n,k)+n-k =c(n-k+i,i-1)+...+c(n-k+i,i)+c(n,k)+n-k =c(n,k-1)+c(n,k)+n-k =c(n+1,k)+n-k   然后lucas定理就可以了 还有个坑爹的地方是要预处理出阶乘mod p和逆元   只需要处理出10000以内的n,m就可以了,因为Lucas有mod嘛   代码: #include<iostream> #include<cstdlib> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> typedef long long LL; using namespace std; const int MAXN=10000; LL prime[1300],path[MAXN]; LL fac[1300][MAXN+5]; LL inv[1300][MAXN+5]; //这里的fac[i][j]和inv[i][j]表示prime[i]的阶乘mod p和它的逆元 bool flag[MAXN+5]; int cnt,mod; LL ksm(LL a,LL k,LL p){ LL ans=1; while(k) { if(k&1) ans=ans*a%p; a=a*a%p; k>>=1; } return ans; } inline void prepare(){ for(int i=2;i<=MAXN;i++) { if(!flag[i]) prime[++cnt]=i,path[i]=cnt;//path是一个小小的hash,降低内存 for(int j=1;j<=cnt;j++) { if(prime[j]*i>MAXN) break; flag[prime[j]*i]=1; if(i%prime[j]==0) break; } } for(int i=1;i<=cnt;i++) { fac[i][0]=inv[i][0]=1; for(int j=1;j<prime[i];j++)//prime[i]之后j就是能被整除了 { fac[i][j]=(fac[i][j-1]*j)%prime[i]; inv[i][j]=ksm(fac[i][j],prime[i]-2,prime[i]); } } return; } LL C(LL n,LL k){ if(n<k) return 0; else if(!k||n==k) return 1; else { LL t=path[mod]; return fac[t][n]*(inv[t][k]*inv[t][n-k]%mod)%mod; } } LL Lucas(LL n,LL k){ if(!k) return 1; else return C(n%mod,k%mod)*Lucas(n/mod,k/mod)%mod; } int main() { prepare(); int n,k,cas=0; while(scanf("%d%d%d",&n,&k,&mod)!=EOF) { if(2*k>n) k=n-k; printf("Case #%d: ",++cas); printf("%lld\n",(Lucas(n+1,k)+n-k)%mod); } }
转载请注明原文地址: https://www.6miu.com/read-78019.html

最新回复(0)