求组合数的多种方法

递推法

C[a][b] = C[a-1][b-1]+C[a-1][b];
很好理解，从一堆苹果中拿出一个苹果，那么从这a个苹果中取出b个苹果可根据有无这个苹果分成两种情况，得到递推式。
模板题：https://www.acwing.com/problem/content/887/
代码：

const int mod = 1e9+7;
int c[N][N];
void col()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) c[i][j]=1;
            else c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
}

公式法

利用组合数公式，求阶乘，再利用快速幂和费马定理求相应的乘法逆元，相乘求得。
模板题：https://www.acwing.com/problem/content/888/

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+7;
const int mod= 1e9+7;
int fact[N];
int qkm(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res  =(long long)res*a%mod;
        b>>=1;
        a=(long long)a*a%mod;
    }
    return res;
}
void init()
{
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<N;i++)
    {
        fact[i] =(long long)fact[i-1]*i %mod;
    }
}
int main(void)
{
    int n;
    scanf("%d",&n);
    init();
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int ans = (long long)fact[a]*qkm(fact[a-b],mod-2)%mod*qkm(fact[b],mod-2)%mod;
        if(a==b) ans =1;
        printf("%d\n",ans);
    }
    
}

卢卡斯定理

当a,b过大时，利用卢卡斯定理求解。
卢卡斯定理

模板题：https://www.acwing.com/problem/content/889/

代码：

#include<bits/stdc++.h>
using namespace std;
int qkm(int a,int b,int p)
{
    int res =1;
    while(b)
    {
        if(b&1) res = (long long)res*a%p;
        b>>=1;
        a=(long long)a*a%p;
    }
    return res;
}
int C(int a,int b,int p)
{
    int res = 1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res = (long long)res*j%p;
        res = (long long) res*qkm(i,p-2,p)%p;
    }
    return res;
}
int lucas(long long a, long long b,int p)
{
    if(a<p && b<p) return C(a,b,p);
    else return (long long)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main(void)
{
    int n;
    cin>>n;
    while(n--)
    {
        long long a,b;
        int p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    
}

高精度

上面几种方法都求的是对一个大素数取模的值。
若要求准确的值则需要用到高精度以及质因数分解。

模板题：https://www.acwing.com/problem/content/submission/890/
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =5010;
int prime[N];
bool st[N];
int cnt;
int sum[N];
int ol(int a)
{
    for(int i=2;i<=a;i++)
    {
        if(!st[i]) prime[cnt++] =i;
            for(int j=0;prime[j]<=a/i;j++)
            {
                st[prime[j]*i] =true;
                if(i%prime[j]==0) break;
            }
    }
}
vector<int> mul(vector<int>a,int b)
{
    int t=0;
    vector<int>c;
    for(int i=0;i<a.size()||t;i++)
    {
        if(i<a.size()) t += a[i]*b;
        c.push_back(t%10);
        t = t/10;
    }
    while(c.size()>1 && c.back()==0) c.pop_back();
    return c;
}
//获取x!中 质因数p的次数
int get(int x,int p)
{
    int res =0;
    while(x)
    {
        res+=x/p;
        x=x/p;
    }
    return res;
}

int main(void)
{
    int a,b;
    scanf("%d%d",&a,&b);
    ol(a);
    for(int i=0;i<cnt;i++)
    {
        int p =prime[i];
        sum[i] = get(a,p)-get(b,p)-get(a-b,p);//存储第i个素数的指数。
    }
    vector<int>res;
    res.push_back(1);
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<sum[i];j++)
        {
            res = mul(res,prime[i]);
        }
    }
    for(int i=res.size()-1;i>=0;i--)
    {
        printf("%d",res[i]);
    }
    
}