卢卡斯定理

标签：int res 定理 卢卡斯 mod define

1.卢卡斯定理用于求解大组合数取模的问题，其中模数必须为素数。
2.卢卡斯定理的具体表述：

\[C^{m}_{n}=C^{b0}_{a0}✖️C^{b1}_{a1}✖️ C^{b2}_{a2}..... C^{bk}_{ak}(mod\quad p)=\prod^{k}_{i=0}C^{bi}_{ai}(mod\quad p); \]

(mod p)表示只在模p的条件下成立
这个式子又等价于

\[C^{m}_{n}=C^{m \% p}_{n\% p}C^{m/p}_{n/p}(mod\quad p); \]

3.这里不证明，因为我不会证明。

模版应用

/**   - swj -
   *         
　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ
 
**/


#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

//----卢卡斯定理--------------
//#define mod 1000000007
int n,m,mod;
int  qpow(int a,int n) //快速幂
{
    int res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

int C(int n,int m)//组合数
{
    if(n<m) return 0;
    if(m>n-m) m=n-m;
    int a=1,b=1;
    for(int i=0;i<m;i++){
        a=(a*(n-i))%mod;
        b=(b*(i+1))%mod;
    }
    return a*qpow(b,mod-2)%mod;
}

int lucas(int n,int m)//卢卡斯定理
{
    if(m==0) return 1;
    return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}

//--------------------------------------



signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;cin>>t;
    while(t--) {
        cin>>n>>m>>mod;
        cout<<lucas(n+m,n)<<endl;
    }
    
}

练习题
P3807 【模板】卢卡斯定理/Lucas 定理
D - Bouquet

标签：int,res,定理,卢卡斯,mod,define
From： https://www.cnblogs.com/swjswjswj/p/18326864