（1）杨辉三角

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
unsigned long long bj[2005][2005],c[2005][2005],z[2005][2005];
int k;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int init(){
    for(int i=0;i<=2000;i++) c[i][0]=c[i][i]=1;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=i;j++){
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    int T=read(); 
    k=read();
    init();
    while(T--){
        int x=read(),y=read();
        cout<<c[x][y]<<'\n';
    }
    return 0;
}

 

（2）Lucas定理

 

 

 

#include<bits/stdc++.h>
using namespace std;
long long x,y;
long long exgcd(long long a,long long b){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int gcd=exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    return gcd;
} 
long long Inv(long long a,long long MOD) {   
    long long d=exgcd(a,MOD);
    return d==1 ? (x%MOD+MOD)%MOD : -1;
}
long long Cm(long long n,long long m,long long p)  {
    long long a=1,b=1;
    if(m>n) return 0;
    while(m){
        a=(a*n)%p;
        b=(b*m)%p;
        m--;
        n--;
    }
    return a*Inv(b,p)%p;  
}
long long Lucas(long long n,long long m,long long p) {
    return m == 0 ? 1 : Cm(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
int main(){
    int  T;
    cin>>T;
    while(T--){
        long long n,m,p;
        scanf("%lld%lld%lld",&n,&m,&p);
        printf("%lld\n", Lucas(n+m,m,p));
    }
    return 0;
}