组合数C（a, b）意为从 a 个物品中选 b 个物品的所有方案数。
公式：a ! / b ! (a - b) !
有时会涉及到 mod p，本文将介绍a b p在不同范围下的组合数求法，这里列举 4 种情况。
情况一：
给定 n 组询问，每组询问给定两个整数 a，b ，请你输出 C(a, b) mod (109+7) 的值。
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一组 a 和 b 。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000 ,
1≤b≤a≤2000
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
解题思路一：
这道题a b 只有 2000，可以考虑预处理2000 * 2000种组合方式来求解，类似于杨辉三角的递推式，因为a b 范围较小，打表即可。
递推式 : c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
证明：借用 y总 的方法，组合a b 即为 从a 个中选出 b 个，那么c[i][j]是怎么推过来的呢，假设 i 个苹果中有一个苹果 t 要选 j个苹果出来的答案就是 选苹果 t + 不选苹果 t ，推一下，假设不选苹果 t ，就是要从剩下的i - 1个苹果中选 j 个，如果选苹果 t 就是从剩下的 i - 1里再选 j - 1 个，证毕。
Code1:
#include <iostream>
using namespace std;
const int N = 2010;
const int 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;//规定 a 0 = 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;
}
return 0;
}
情况二：
给定 n 组询问，每组询问给定两个整数 a，b ，请你输出 C(a, b) mod (109+7) 的值。
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一组 a 和 b 。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000 ,
1≤b≤a≤105
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
解题思路二：
a b 的范围有 1e5, n 有 1e4 此时再打表已经是1e5 * 1e5 显然不行，从定义出发，组合数公式为 a! / b! (a - b)! 可以预处理出1e5 的阶乘的所有情况，但是涉及到除法 % 1e9 + 7，可以通过逆元将其转化为乘法 % 1e9 + 7 ，1e9 + 7是素数，费马小定理 + 快速幂推逆元即可。O(1) 的时间输出结果。
Code2：
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
const int mod = 1e9 + 7;
int fact[N], infact[N];//i的阶乘和阶乘的逆元（mod 1e9 的情况）
int n;
int qpow(int a, int b, int p)//快速幂板子套费马小定理
{
int res = 1;
while (b)
{
if (b & 1) res = (ll)res * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return res;
}
int main()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++)//预处理所有数的阶乘及逆元
{
fact[i] = (ll)fact[i - 1] * i % mod;
infact[i] = (ll)infact[i - 1] * qpow(i, mod - 2, mod) % mod;
}
cin >> n;
while (n --)
{
int a, b;
cin >> a >> b;
int ans = (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;//从定义出发求解
cout << ans << endl;
}
return 0;
}
情况三：
给定 n 组询问，每组询问给定三个整数 a,b,p ，其中 p 是质数，请你输出 C(a, b) mod p 的值。
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一组 a,b,p 。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤20 ,
1≤b≤a≤1018 ,
1≤p≤105 ,
输入样例：
3
5 3 7
3 1 5
6 4 13
输出样例：
3
3
2
解题思路三：
这种情况下的a b 非常大，显然预处理行不通了，n 只有20，可以考虑卢卡斯定理求组合数，那么卢卡斯定理：
C(a, b) ≡ C(a % p, b % p) + C(a / p , b / p) (mod p)
可以利用卢卡斯定理求解，p 只有1e5，当 a, b都 < p 时，直接从定义出发递推C(a, b) 即可。如果比 P 大则继续套卢卡斯。
p 是质数，求逆元时直接套费马小定理即可。
Code3：
#include <iostream>
using namespace std;
typedef long long ll;
int p;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = (ll)res * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return res;
}
int c(int a, int b)
{
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j --)
{
res = (ll)res * j % p;
res = (ll)res * qpow(i, p - 2) % p;
}
return res;
}
int lucas(ll a, ll b)
{
if (a < p && b < p) return c(a, b);
return (ll)c(a % p, b % p) * lucas(a / p, b / p) % p;;
}
int main()
{
int n;
cin >> n;
while (n --)
{
ll a, b;
cin >> a >> b >> p;
cout << lucas(a, b) << endl;
}
return 0;
}
情况四：
输入 a,b ，求 C(a, b) 的值。
输入格式
共一行，包含两个整数 a 和 b 。
输出格式
共一行，输出 C(a, b) 的值。
数据范围
1≤ b ≤ a ≤5000
输入样例：
5 3
输出样例：
10
解题思路四：
这道题范围只有 5000 ，但是没有涉及到取模运算，数非常大，需要用到高精度，套公式的话还有除法，逆元没法求，写一个高精度除法非常麻烦，可以优化一下，分解质因数，分子分母约分，最后就可以变成p0a0 p1a1 … pkak 了，这里分解一下质因数，因为是阶乘，阶乘中取质因子的方法是，a / p + a / p2 + … + a / pn，因为 p 的倍数含有一个p， pn 含有 n 个 p，所以可以通过相加得到。
Code4：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5050;
int prime[N], cnt;
bool st[N];
int p[N];
void init()//涉及到质因子，先筛素数
{
for (int i = 2; i < N; i ++)
{
if (!st[i])
{
prime[cnt++] = i;
for (int j = i + i; j < N; j += i)
st[j] = true;
}
}
}
int solve(int n, int t)//看n贡献了几个t
{
int res = 0;
while (n)
{
res += n / t;
n /= t;
}
return res;
}
vector<int > mul(vector<int > &a, int b)//高精度 * 低精度模板
{
vector<int > res;
for (int i = 0, t = 0; i < a.size() || t; i ++)
{
if (i < a.size()) t += a[i] * b;
res.push_back(t % 10);
t /= 10;
}
while (!res.back() && res.size() > 1) res.pop_back();
return res;
}
int main()
{
int a, b;
cin >> a >> b;
init();
for (int i = 0; i < cnt && prime[i] <= a; i ++)
{
int t = prime[i];
p[i] = solve(a, t) - solve(b, t) - solve(a - b, t);
}
vector<int > ans;
ans.push_back(1);
for (int i = 0; i < cnt; i ++)
for (int j = 1; j <= p[i]; j ++)
ans = mul(ans, prime[i]);
for (int i = ans.size() - 1; i >= 0; i --) cout << ans[i];
cout << endl;
return 0;
}