求组合数1：

题目链接：885. 求组合数 I - AcWing题库

题面：

第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

1<=n<=10000

1<=b<=a<=2000

 由此我们可以得到：c[a][b]=c[a-1][b-1]+c[a-1][b]

由于数据范围很小，我们可以预处理出来所有的c[a][b],时间复杂度为O(a*b)

代码为：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{
    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]+c[i-1][j-1])%mod;
        }
    }
}
int main()
{
    IOS;
    init();//预处理
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}

 

求组合数2

题目链接：886. 求组合数 II - AcWing题库

题面：

1<=n<=10000

1<=b<=a<=1e5

这里如果还用上面的预处理，时间复杂度就是O(1e5*1e5)会超时。

计算组合数的数学公式是：c[a][b]=a! / (a-b)!*b! 。

由于这里有除法、取模，需要用到乘法逆元，即

   =

具体推导公式看这个博客：快速幂模板求逆元，逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数_吴雨4的博客-CSDN博客https://blog.csdn.net/WSY444/article/details/125582397?spm=1001.2014.3001.5502

基本思路就是：先计算出每个数的阶乘，即a！。

再算出每个数逆元的阶乘，即！。

注意0的阶乘是1。

代码：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
const int N=100010,mod=1e9+7;
//快速幂模板
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}
int fact[N];//存每个数的阶乘，即a！
int infact[N];//存每个数逆元的阶乘，即 b^(-1) ！
int main()
{
    IOS;
    fact[0]=infact[0]=1;//零的阶乘是1
    for(int i=1;i<=N;i++)
    {
        fact[i]=(ll)fact[i-1]*i%mod;
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(ll)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
    return 0;
}