组合数学

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
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

`#include
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
            inv[i]=inv[i-1]*i%mod;
            ninv[i]=qpow(inv[i],mod-2,mod);
        }
        coutlucas(n+m,n,mod)"\n";
    }
    return 0;
}`