组合数

1、求组合数，从a中选b个数的方案：

#include <iostream>
using namespace std;
const int N = 2001, 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()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a, b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
}

从a中选b个的方案 = 假如先拿出一个，然后剩下的a-1个选b个的方案（不包含拿出的这个数，所以要选b个） + 剩下的a-1个选b-1个的方案（包含拿出的这一个数，所以要选b-1个）之和。

 首先预处理出所有的方案数，时间复杂度为2000 * 2000 = 4e6;

注意边界c[i][0] (0 <= i <= N) c[i][0] = 1;

1）n<=1e5,  1<=a,b<=2000 用的是递推c[a][b] = c[a-1][b] + c[a-1][b-1];

2）n<=1e4, 1<=a,b<=1e5, 预处理 Cab = a! / b! * (a - b)!, fact[i] = i! mod 1e9+7; a / b mod p != a mod p / b mod p, 用逆元来算，把除法变成乘法。

预处理初阶乘的逆元：infact[i] = i!^-1 mod 1e9 + 7;

组合数

原文：https://www.cnblogs.com/longxue1991/p/12731725.html