lucas定理-白红宇

lucas定理

阅读量：6602 次

发布时间：2019-06-24

本文共 2009 字，大约阅读时间需要 6 分钟。

Lucas定理：

A,B是非负数,p是质数,

A可以写成p进制a[n]....a[0],B可以写成p进制b[n]......b[0]

则组合数C(a,b) = C(a[n],b[n])*.....*C(a[0],b[0])

我们借此实现组合数取模，Lucas(a,b,p) = C(a%p,b%p)*Lucas(a/p,b/p,p);

对于C(a,b) = a!/(b!*(a-b)!),

对此我们可以利用费马小定理,a^(p-1) = 1(mod p) ->a*a^(p-2) = 1

所以1/(b!*(a-b)!) = (b!*(a-b)!)^(p-2)

参考：

hdu 3037

求C(n+m,m)%p，模板题

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;typedef long double ld;const ld eps=1e-10;const int inf = 0x3f3f3f;const int maxn = 100005;ll fac[maxn];ll pow_mod(ll a,ll b,ll mod){ ll ret = 1; while(b) { if(b & 1) ret = (ret*a)%mod; a = (a*a)%mod; b >>= 1; } return ret;}ll Fac(ll p){ fac[0] = 1; for(int i = 1;i <= p;i++) { fac[i] = (fac[i-1] * i)%p; }}ll lucas(ll n,ll m,ll p){ ll ret = 1; while(n && m) { ll a = n % p; ll b = m % p; if(a < b) return 0; ret = (ret*fac[a]*pow_mod(fac[b]*fac[a-b]%p,p-2,p))%p; n /= p; m /= p; } return ret%p;}int main(){ int t; scanf("%d",&t); while(t--) { ll a,b,p; scanf("%I64d%I64d%I64d",&a,&b,&p); Fac(p); ll ans = lucas(a+b,b,p); printf("%I64d\n",ans); }}

hdu 4349

lucas定理的拓展

直接用lucas超时- -

对于每个C(n,0)....C(n,n),利用lucas定理把它们看成二进制数,于是根据分解公式我们可以看成C(a[n],b[n])*.....*C(a[0],b[0])，

可以发现C(1,1) = C(1,0) = C(0,0) = 1; C(0,1) = 0;所以当a中为0的位置b也为0时我们才可能得到1，

于是成了统计a中1的个数num。然后2^num得出b可能有多少种即可

例：

C(21,20) 10100 10101

C(1,1)*C(0,0)*C(1,1)*C(0,0)*C(1,0) = 1.

C(21,18)

10010 10101

C(1,1)*C(0,0)*C(1,0)*C(0,1)*C(1,0) = 0.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;typedef long double ld;const ld eps=1e-10;const int inf = 0x3f3f3f;const int maxn = 100005;int main(){ ll x; while(scanf("%I64d",&x) != EOF) { ll num = 0; while(x) { if(x & 1) num++; x >>= 1; } printf("%I64d\n",(ll)1<