组合数学

用户头像 发布于 1 天前 12 次阅读 OI

组合数学

P3807 【模板】卢卡斯定理 / Lucas 定理

(nm) mod p=(⌊np⌋⌊mp⌋)⋅(n mod pm mod p) mod p\begin{aligned} \begin{pmatrix} n \\ m \end{pmatrix} \ mod \ p = \begin{pmatrix} \lfloor \frac{n}{p} \rfloor \\ \lfloor \frac{m}{p} \rfloor \end{pmatrix} \cdot \begin{pmatrix} n\ mod\ p \\ m\ mod\ p \end{pmatrix} \ mod \ p \\ \\ \end{aligned}

证明略，网上一堆。代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int T;
int inv[N],ninv[N];

int qpow(int x,int y,int mod){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        y>>=1,(x*=x)%=mod; 
    }
    return res;
}

int C(int n,int m,int mod){
    if(m>n) return 0;
    return inv[n]*ninv[m]%mod*ninv[n-m]%mod;
}

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

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        int n,m,mod;
        cin>>n>>m>>mod;
        inv[0]=1;
        for(int i=1;i<=mod;i++){
            inv[i]=inv[i-1]*i%mod;
            ninv[i]=qpow(inv[i],mod-2,mod);
        }
        cout<<lucas(n+m,n,mod)<<"\n";
    }
    return 0;
}