递推法 $O(n^2)$

#include<cstdio>

using namespace std;

const int N=2000+5,mod=1e9+7;
int f[N][N];

int main()
{
    for(int i=1;i<N;i++)    f[i][0]=f[i][i]=1;
    for(int i=2;i<N;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;

    int T;  scanf("%d",&T);
    while(T--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",f[a][b]);
    }
    return 0;
}

预处理阶乘和逆元$O(n^2)$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

const int N=1e5+5,mod=1e9+7;
int fact[N],infact[N];

int read()
{
    char ch;
    while((ch=getchar())==' ' || ch=='\n'  || ch=='\r');
    int f=1,ret=0;
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }   
    while(ch>='0'  && ch<='9')
    {
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret*f;
} 

int qpow(ll a,int n)
{
    ll ret=1;
    while(n)
    {
        if(n&1) ret=ret*a%mod;
        a=a*a%mod;
        n>>=1; 
    }
    return ret;
}

int C(int a,int b)
{
    return (ll)fact[a]*infact[b]%mod*infact[a-b]%mod;
}

int main()
{
    fact[0]=1;  infact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=(ll)i*fact[i-1]%mod;
        infact[i]=(ll)infact[i-1]*qpow(i,mod-2)%mod;
    }

    int T;  cin>>T;
    while(T--)
    {
        int a,b;
        a=read();
        b=read();
        printf("%d\n",C(a,b));
    }
    return 0;
}

Lucas定理 适合a b很大，但是模为质数

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

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

ll qpow(ll a,int n,int mod)
{
    ll ret=1;
    while(n)
    {
        if(n&1) ret=ret*a%mod;
        a=a*a%mod;
        n>>=1; 
    }
    return ret;
}

ll C(int a,int b,int p)
{
    if(a<b) return 0;
    ll up=1,down=1;
    for(int i=a,j=1;j<=b;j++,i--)
    {
        up=i*up%p;
        down=j*down%p;
    }
    return up*qpow(down,p-2,p)%p;
}

ll lucas(ll a,ll b,int p)
{
    if(a<p && b<p)  return C(a,b,p);
    return lucas(a/p,b/p,p)*C(a%p,b%p,p)%p;
}

int main()
{
    int T;  cin>>T;
    while(T--)
    {
        ll a,b;
        a=read();
        b=read();
        int p=read();
        printf("%d\n",lucas(a,b,p));
    }
    return 0;
}

分解质因数+高精度乘法

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

const int N=5005;
int primes[N],cnt,vis[N];
int sum[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            vis[i*primes[j]]=1;
            if(i%primes[j]==0)  break;
        }
    }
}

int get(int a,int p)
{
    int ret=0;
    for(int i=a;i;i/=p) ret+=i/p;
    return ret;
}

vector<int> mul(vector<int> a,int b)
{
    vector<int> c;
    int t=0;
    for(auto &x:a)
    {
        t+=x*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
}

int main()
{
    init(N-1);
    int a,b;
    cin>>a>>b;
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }
    vector<int> ans;
    ans.push_back(1);
    for(int i=0;primes[i]<=a;i++)
        for(int j=1;j<=sum[i];j++)
            ans=mul(ans,primes[i]);
    int len=ans.size()-1;
    for(int i=len;~i;i--)
        printf("%d",ans[i]);
    cout<<endl;
    return 0;
}