卢卡斯定理&&中国剩余定理

卢卡斯定理（模数较小，且是质数）

式子C(m,n)=C(m/p,n/p)*C(m%p,n%p)%p

至于证明（我也不会QAQ，只要记住公式也该就好了）。

同时卢卡斯定理一般用于组合数取模上

1.首先当组合数取得模较大时，我们可以使用卢卡斯，也可以直接求

（只要数据范围不是很大，还能开得起数组，我们可以直接预处理出阶乘，逆元，需要时O(1)求，当然要是质数，不然只能现求）。

2.当组合数的模很小时，我们只能用卢卡斯，

我们可以发现假如我们照旧求的话，可能有的阶乘直接被消成0了

这个时候直接用阶乘会不准确，那么只能lusca了

3.模数非质数时，例如多个质数相乘，我们先用质因数分解，在用中国剩余定理即可。

 1 ll pow(ll x,ll y,ll mod)

 2 {

 3     ll ans=1;

 4     if(y==0)return 1;

 5     while(y)

 6     {

 7        if(y&1)ans=ans*x%mod;

 8        x=x*x%mod;

 9        y>>=1;

10     }

11     return ans%mod;

12 }

13 ll C(ll x,ll y,ll mod)

14 {

15     if(y>x)return 0;

16     if(y==0)return 1;

17     return jie[x]*pow(jie[y]*jie[x-y]%mod,mod-2,mod)%mod;

18 }

19 ll lus(ll x,ll y,ll mod)

20 {

21    if(y>x)return 0;

22    if(y==0)return 1;

23    return lus(x/mod,y/mod,mod)*C(x%mod,y%mod,mod)%mod;

24 }

卢卡斯模板

一道例题

中国剩余定理：

设m1,m2,m3,m4....mk两两互素，则同余方程组

x≡a1(mod m1)

x≡a2(mod m2)

x≡a3(mod m3)

x≡a4(mod m4)

x≡ak(mod mk)

一定有解，x≡(a1*M1*M1^(-1)+a2*M2*M2^(-1)+....)(mod M)

其中M=m1*m2*m3*....mk,Mi=M/mi,Mi^(-1)是Mi在模mi意义下的逆元。

至于证明自己可以在书上看了。。。。

代码

 1 void exgcd(ll a,ll b,ll &x,ll &y)

 2 {

 3    if(b==0){

 4       x=1;y=0;return ;

 5    }

 6    exgcd(b,a%b,x,y);

 7    ll z=x;x=y;y=z-(a/b)*y;

 8    return ;

 9 }

10 ll sum;ll len=1;

11 void CRT()

12 {

13    for(ll i=0;i<su.size();++i)

14    {

15       len*=su[i];

16       //printf("%lld\n",len);

17    }

18    for(ll i=0;i<su.size();++i)

19    {

20       M[i]=len/su[i];

21    }

22    for(ll i=0;i<su.size();++i)

23    {

24         ll x,y;

25         exgcd(M[i],su[i],x,y);

26         x=(x+su[i])%su[i];

27         sum=(sum+ans[i]*M[i]*x)%len;

28         //printf("sum=%lld ans=%lld M=%lld x=%lld\n",sum,ans[i],M[i],x);

29    }

30    printf("%lld\n",sum);

31 }

m=∏ni=1mi,Mi=m/mi

m=∏ni=1mi,Mi=m/mim=∏ni=1mi,Mi=m/mi

m=∏ni=1mi,Mi=m/mi

巴特西

卢卡斯定理&&中国剩余定理

最新文章

热门文章