组合数 求余 C(n,m,p)

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

long long res[67][67]= {0};
long long cal(int n,int m,int p) {
    if(n==m||m==0) {
        return 1;
    }
    if(res[n][m]!=0) return res[n][m];
    return res[n][m]=(cal(n-1,m,p)+cal(n-1,m-1,p))%p;
}

void cal1(int n,int m,int p) {
    for(int i=0; i<=n; i++) {
        res[i][i]=res[i][0]=1;
    }
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=n/2; j++) {
            res[i][j]=(res[i-1][j]+res[i-1][j-1])%p;
            res[i][i-j]=res[i][j];
        }
    }
    return ;
}

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

const int Max=1e5;
int prime[Max],num=0;
bool a[Max]= {0};
void f() {
    for(int i=2; i<Max; i++) {
        if(!a[i]) {
            prime[num++]=i;
        }
        for(int j=i+i; j<Max; j+=i) {
            a[j]=1;
        }
    }
    return ;
}

int C(int n,int p) {
    if(n<p) {
        return 0;
    }
    return n/p+C(n/p,p);
}

int binaryPow(int a,int b,int c){
    int ans=1;
    while(b>0){
        if(b&1){
            ans=ans*a%c;
        }
        a*=a%c;
        b/=2;
    }
    return ans;
}

int cal2(int n,int m,int p) {
    f();
    int ans=1;
    for(int i=0; i<num&&prime[i]<=n; i++) {
        int c=C(n,prime[i])-C(m,prime[i])-C(n-m,prime[i]);
        ans=ans*binaryPow(prime[i],c,p)%p;
    }
    return ans;
}

int main() {
    int n,m,p;
    while(cin>>n>>m>>p) {
        cout<<cal(n,m,p)<<endl;
        cout<<lucas(n,m,p)<<endl;
        cout<<cal2(n,m,p)<<endl;
    }
    return 0;
}