# 卢卡斯定理 + 组合数板子

题链

给出n,m,p，计算C(n,m)是否等于p；(1<=n<=1e9,0<=m<=1e5,1<=p<=10^{4e5})

等式两边都对质数取模，如果对多个质数取模后计算结果都得出等式两边相同，那么可以很大概率认为这两个数相等。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=4e5+5;
LL primer[]={1000003,1000849,1000999,1001069,1259677,1259477};
LL P=1000003;
char s[maxn];
LL n,m;
LL qpow(LL a,LL b){
    LL ans=1;
    a%=P;
    while (b){
        if(b&1)ans=ans*a%P;
        a=a*a%P;
        b>>=1;
    }
    return ans;
}
LL C(LL n,LL m){
    if(m==0)return 1;
    if(m>n-m)m=n-m;

    LL fz=1,fm=1;//分别计算分子和分母
    for(int i=1;i<=m;++i){
        fz=fz*(n-i+1)%P;
        fm=fm*i%P;
    }
    /*cout<<"fz"<<fz<<endl;
    cout<<"fm"<<fm<<endl;
    cout<<"qp"<<qpow(fm,P-2)<<endl;
    cout<<":::"<<fz*qpow(fm,P-2)%P<<endl;*/
    return fz*qpow(fm,P-2)%P;
}
LL lucas(LL n,LL m){
    if(m==0)return 1;
    return lucas(n/P,m/P)%P*C(n%P,m%P)%P;
}
int main(){
    /*cout<<qpow(2,10)<<endl;
    cout<<C(10,3)<<endl;
    cout<<lucas(10,3);*/
    scanf("%lld %lld %s",&n,&m,s);
    int len=strlen(s);
    for(int i=0;i<6;++i){
        P=primer[i];

        LL t=0;
        for(int j=0;j<len;++j)t=(t*10+(s[j]-'0'))%P;

      //  cout<<"t"<<t<<endl;
        if(lucas(n,m)!=t){
            printf("No!
");
            return 0;
        }
    }
    printf("Yes!
");
    return 0;
}