Acwing 组合计数

一个递推式：
$$\begin{gathered} 从a个元素中选择b个，有多少种取法C_a^b=\frac{a\times (a-1)\times \cdots \times (a-b+1)}{1\times 2\times 3\times \cdots \times b} \\ =\frac{a!}{b!\times (a-b)!} \\ =C_{a-1}^b+C_{a-1}^{b-1} \end{gathered}$$
Acwing 855.求组合数 I

实现思路：询问10000次，数字范围2000，直接使用递推式

• 递推式：
  $$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$$
  其实就是动态规划DP，$O(n^2).$
• 因为数字范围就2000，直接先预处理出2000范围内的所有组合数，使用二维数组存储c[][],后续只需调用就行
• 注意结果要取模，防止结果超出int范围

具体实现代码（详解版）：

#include <iostream>using namespace std;const int N = 2010,mod = 1e9+7;
int c[N][N];//预处理出这2000范围内的所有组合数
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(){int n;cin >> n;init();while(n --){int a,b;cin >> a >> b;cout << c[a][b] << endl;}return 0;
}

如果数据范围变大，递推的效率就会变低，超时！看下面的题目：
Acwing 886.求组合数II

实现思路：这是使用公式+乘法逆元的方法预处理得到阶乘
$$公式C_a^b=\frac{a!}{b!\times (a-b)!}$$

• 考虑到计算过程存在取模且公式存在分式，则需要将除法转化为乘法，因为除法取模会得到错误答案，所以转化为乘法再做取模运算，这时就想到乘法逆元（因为本题模数1e9+7是质数，所以可以使用快速幂求逆元，费马定理b^(m-2)。注意若没有对质数取模，则只能用扩展欧几里得算），对分母两个数分别取逆元再乘以分子，即可得到答案
• 设置一个数组fact[]，表示分子阶乘；数组infact[]，表示分母阶乘的逆元，最后通过fact[a]*infact[b]*infact[a-b]得到组合数结果
  具体实现代码（详解版）

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL; 
const int N = 100010; 
const int mod = 1e9 + 7; // 模数 (10^9 + 7)// 阶乘数组和阶乘逆元数组
LL fact[N], infact[N];// 快速幂函数，计算 (a^k) % p
LL qmi(LL a, LL k, LL p) {LL res = 1; // 初始化结果为 1LL t = a % p; // 基数 a 取模// 进行快速幂计算while (k) {if (k & 1) // 如果当前位为 1res = (res * t) % p; // 更新结果t = (t * t) % p; // 基数平方并取模k >>= 1; // 右移 k，处理下一位}return res; // 返回结果
}int main() {// 初始化阶乘和逆元fact[0] = infact[0] = 1; // 0! = 1for (int i = 1; i < N; i++) {fact[i] = (fact[i - 1] * i) % mod; // 计算阶乘infact[i] = (infact[i - 1] * qmi(i, mod - 2, mod)) % mod; // 计算阶乘的逆元}int n; cin >> n; while (n--) {int a, b; cin >> a >> b; // 计算并输出组合数 C(a, b)cout << (fact[a] * infact[b] % mod * infact[a - b] % mod) << endl;}return 0; 
}

如果数据范围继续增大，可以考虑使用Lucas定理
Acwing 887.求组合数III

• 卢卡斯（lucas）定理：
• $$C_a^b\equiv C_{amodp}^{bmodp}\times C_{a/p}^{b/p}(\mathrm{mod}p)$$
  lucas函数：函数的参数为a,b，若a<p且b<p则说明a,b足够小可以通过组合数函数C(a,b)直接计算，否则返回C（a%p,b%p）*lucas(a/p,b/p)（因为a,b除p可能依然很大，当足够小时就像上述情况直接返回组合数函数）
• 注意这里求组合数C，与上题不同，无需枚举处理所有组合数，直接用基本公式：
  -$$C_a^b=\frac{a\ast (a-1)...\ast (a-b+1)}{b!}$$
• 采用类似双指针算法，指针i由后向前遍历到a-b+1，j由1向前遍历到b
• 然后再利用乘法逆元（快速幂求逆元），将除法转化为乘法，取模

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL; // 定义长整型别名
const int N = 100010; // 最大支持的 n 值
const int mod = 1e9 + 7; // 模数LL fact[N], infact[N]; // 分子阶乘数组，分母阶乘的逆元数组// 快速幂算法，用于计算 (a^k) % p
LL qmi(LL a, LL k, LL p) {LL res = 1; // 结果初始值为 1LL t = a % p; // 基数 a 取模while (k) {if (k & 1) { // 如果 k 的当前位为 1res = (res * t) % p; // 更新结果}t = (t * t) % p; // 基数平方并取模k >>= 1; // 右移 k，处理下一位}return res; // 返回结果
}// 基本公式求组合数，利用乘法逆元
int C(int a, int b, int p) {if (b < 0 || a < 0 || a < b) return 0; // 检查 b 是否负数，或者 a 是否小于 bLL x = 1, y = 1; // x 是分子，y 是分母for (int i = a, j = 1; j <= b; i--, j++) {x = (x * i) % p; // 计算分子y = (y * j) % p; // 计算分母}return x * (LL)qmi(y, p - 2, p) % p; // 返回组合数
}// Lucas 定理计算组合数
int lucas(LL a, LL b, int p) {if (a < p && b < p) return C(a, b, p); // 基本情况// 递归计算return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}int main() {int n; // 测试案例的数量cin >> n; // 输入测试案例数量while (n--) {LL a, b, p; // a 和 b 为组合数参数，p 为模数cin >> a >> b >> p; // 输入 a、b 和 pcout << lucas(a, b, p) << endl; // 输出结果}return 0;
}

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用，同时需要用到高精度乘法。
Acwing 888.组合计数IV

实现思路：

• 使用组合数公式
  $$C_a^b=\frac{a!}{b!\times (a-b)!}$$

• 用线筛法求出对于公式中最大的数a之前的所有的质数，之后在得到在a!的中所包含的每个质因子p对应的幂次
  $$a!中质因子p的幂次=\frac{a}{p}+\frac{a}{p^2}+.....\frac{a}{p^n}，向下取整$$

• 同理得到b!和(a-b)!中对应p的质因子的幂次，然后a!中p的幂次-b!中p幂次-(a-b)!中p的幂次=结果中p的幂次，以此类推得到结果中每个质因子pi对应的幂次$$最终结果C_a^b=p_1^{\alpha 1}\ast p_2^{\alpha 2}\ast p_3^{\alpha 3}\ast ....\ast p_k^{\alpha k}$$

• 再对结果进行一个高精度的乘法得到最终结果

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 5010; 
int primes[N], cnt;
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否被筛掉// 线性筛法求素数
void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i; // 如果当前数为质数，则存储// 标记合成数for (int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true; // 标记 primes[j] * i 为合成数if (i % primes[j] == 0) break; // 防止重复标记}}
}// 计算质因数的次数
int get(int n, int p) {int res = 0;while (n) {res += n / p; // 计算 n! 中 p 的次数n /= p; // 继续向下除以 p}return res;
}// 高精度乘法
vector<int> mul(vector<int> a, int b) {vector<int> c; // 存储乘法结果int t = 0; // 进位for (int i = 0; i < a.size(); i++) {t += a[i] * b; // 逐位乘以 bc.push_back(t % 10); // 当前位t /= 10; // 更新进位}// 处理最后的进位while (t) {c.push_back(t % 10);t /= 10;}return c; 
}int main() {int a, b;cin >> a >> b; get_primes(a); // 预处理范围内的所有质数// 求每个质因数的次数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> res; // 存储结果res.push_back(1); // 初始化高精度数为 1// 用高精度乘法将所有质因子相乘for (int i = 0; i < cnt; i++) {//遍历所有质因子for (int j = 0; j < sum[i]; j++) {res = mul(res, primes[i]); // 对应幂次循环}}for (int i = res.size() - 1; i >= 0; i--) cout << res[i];return 0; 
}

用到了之前的高精度乘法、线性筛法求素数等，所以难题都是可以分解的，每部分都是模板题。
卡特兰数
Acwing 889.满足条件的01序列

思路分析：

• 将01序列置于坐标系中，起点定于原点。若0表示向右走，1表示向上走，那么任何前缀中0的个数不少于1的个数就转化为：路径上的任意一点，横坐标大于等于纵坐标。题目所求即为这样的合法路径数量。
• 下图中，表示从(0,0)到（n,n)的路径，在绿线即以下表示合法，若触碰红线则不合法。
  

由图可知，任何一条不合法的路径（如黑色路径），都对应一条从(0,0)走到(n-1,n+1)的一条路径(如灰色路径）.而任何一条(0,0)走到(n-1,n+1)的路径，也对应了一条从(0,0)走到(n,n)的不合法路径。

假设有6个0，6个1，设0表示向右走一步，1表示向上走一步，则路径是从原点（0,0）到点(6,6)，需要12步。根据题目要求前缀中0的个数大于1的个数，转化为所走路径要满足的条件就是：路径上的每一点的坐标都必须满足横坐标x>=纵坐标y，即路径必须在图中红色斜线(y=x+1)的下方，不能与红色斜线有交叉。目标点（6,6）关于红色斜线对称的点为（5,7），则只要是从原点（0,0）走到（5,7）的路径必然会与红线有交叉，即不符合路径的要求。
（0,0）–> （6，6）的路径方案数：C_{12}^{6} （总方案）

（0,0）–> （5，7）的路径方案数：C_{12}^{5} (不符合条件的方案)
故符合条件的方案数C_{12}^{6} - C_{12}^{5}
$$\begin{gathered} 由以上推广到n个0和n个1，得到公式: \\ {C}_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}=\frac{(2n)!}{(n+1)!n!}，即卡特兰数 \end{gathered}$$
注：这里结果依旧要对一个质数取模，所以可以用费马定理，快速幂求逆元

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int mod = 1e9 + 7;
typedef long long LL; // 快速幂
LL qmi(int a, int k, int p) {int res = 1; // 初始化结果为1int t = a; // 初始化当前基数while (k) { // 当 k 不为0if (k & 1) res = (LL)res * t % p; // 当 k 的当前位为1，乘入当前基数t = (LL)t * t % p; // 当前基数平方k >>= 1; // 右移 k，准备下一轮}return res; 
}// 用组合数基本公式求卡特兰数
LL Katelan(int n) {int a = 2 * n, b = n; // 2n 和 nLL res = 1; // 初始化结果for (int i = a, j = 1; j <= b; j++, i--) {res = (LL)res * i % mod; // 计算 (2n)! / n!res = (LL)res * qmi(j, mod - 2, mod) % mod; // 乘以 (n!) 的逆元}return (LL)res * qmi(n + 1, mod - 2, mod) % mod; // 乘以 (n+1) 的逆元
}int main() {int n;cin >> n; LL res = Katelan(n); cout << res << endl; return 0; // 程序结束
}

以上就是关于组合数的几种计算方法，我们要根据数据的大小范围确定使用哪种方法，对于最后的卡特兰数，就是组合数的一个应用。它是从一个01序列的问题推出来的，比较有技巧性。