P3807

· · 个人记录

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

对于 p 是质数，有：

C_n^m\equiv C_{n\bmod p}^{m\bmod p}C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}\pmod{p}

然后预处理+递归求解即可。

显然这是一个与除法有关的复杂度。

时间复杂度 O(Tp\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e5;

ll T,n,m,p;

ll fac[N+5];

inline ll pow(ll b,ll p,ll mo) {
    ll res=1;
    while(p) {
        if(p&1) res=(res*b)%mo;
        b=(b*b)%mo;p>>=1;
    }
    return res;
}

inline ll C(ll n,ll m) {
    if(m>n) return 0;
    return (((fac[n]*pow(fac[m],p-2,p))%p)*pow(fac[n-m],p-2,p))%p;
}

inline ll Lucas(ll n,ll m) {
    if(!m) return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    T=read();

    while(T--) {
        n=read();m=read();p=read();
        fac[0]=1;
        for(ll i=1;i<=p;i++) {
            fac[i]=(fac[i-1]*i)%p;
        }
        writeln(Lucas(n+m,n));
    }

    return 0;
}