求组合数 C++

题目一 求组合数1

解题思路

1. 预处理C^b_a,代入上述公式即可，时间为2000 * 2000(a*b);
2. 查表输出
   注：C_a⁰=1;

代码实现

#include<iostream>using namespace std;const int N = 2010, mol = 1e9 + 7;
int c[N][N];
int n;int main()
{for (int i = 0; i <= 2000; i ++ )//预处理{for (int j = 0; j <= i;j ++ ){if (j == 0){c[i][j] = 1;}else{c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mol;}}}cin >> n;int a, b;while(n -- )//查表输出{scanf("%d%d", &a, &b);printf("%d\n", c[a][b]);}return 0;
}

题目二 求组合数2

解题思路

原链接：https://www.acwing.com/solution/content/135922/

具体步骤

1. C_a^b = a! * b!^-1 * (a-b)^-1(注： a^-1指a在模运算下的逆元，不是1/a)；
2. 预处理递归求出fact[a] (a!), infact[a] (a!^-1) (1<=a<=1e5);
3. 直接递归算出fact[a], 用快速幂算出infact[a];
   (快速幂传送门：https://blog.csdn.net/m0_62112384/article/details/142786715)
4. 代入公式1，查表求出结果；

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10, M = 1e9 + 7;
typedef long long LL;LL fact[N], infact[N];//fact[i] 是求i的阶乘，infact[i]是求i!的逆元LL qmi(LL a, LL b, LL m)//快速幂
{LL res = 1;while (b){if (b & 1){res = res * a % m;}b >>= 1;a = a * a % m;}return res;
}int main()
{fact[0] = infact[0] = 1;for (int i = 1; i <= N; i ++ ){fact[i] = fact[i - 1] * i % M;infact[i] = infact[i - 1] * qmi(i, M - 2, M) % M;//快速幂求逆元}int n, a, b;cin >> n;while (n -- ){scanf("%d%d", &a, &b);cout << fact[a] % M * infact[b] % M * infact[a - b] % M << endl;//在答案中多模几次M，防止爆long long}return 0;
}

题目三 卢卡斯算法求组合数3

解题思路

原解题链接：https://www.acwing.com/solution/content/5244/

代码实现

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;
int p;LL qmi(LL a, LL b)//快速幂
{LL res = 1;while (b){if (b & 1){res = res * a % p;}b >>= 1;a = a * a % p;}return res;
}LL C(LL a, LL b)//求组合数（按定义求）
{LL res = 1;for (int i = a, j = 1; j <= b; j ++ , i -- ){res = res * i % p;res = res * qmi(j, p - 2) % p;}return res;
}LL lucas(LL a, LL b)
{if (a < p && b < p){return C(a, b) % p;}return C(a % p, b % p) * lucas(a / p, b / p) % p;
}int main()
{int n;LL a, b;cin >> n;while (n -- ){scanf("%lld%lld%d", &a, &b, &p);cout << lucas(a, b) << endl;}return 0;
}

题目四 高精度求组合数

解题思路

如何分解阶乘的质因数：
要求a!中质数p的指数，则p的指数=[a/p] + [a/p²] + [a/p³]…
举例：求8!中分解质因数后2的指数是多少?
解：2的指数 = [8/2] + [8/2²] + [8/2³] = 7,则8!分解质因数后含有2⁷这一项。

1. 筛质数
2. 分解质因数，求出每个质数在组合数分解质因数后的指数
3. 代入高精度乘法求解

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 5010;int primes[N], cnt;
bool st[N]; 
int idx[N];//idx[i]代表primes[i]的指数;void get_primes(int n)//线性筛法求质数
{for (int i = 2;i <= n;i ++ ){if (!st[i]){primes[cnt ++] = i;}for (int j = 0; primes[j] * i <= n; j ++){st[primes[j] * i] = true;if (i % primes[j] == 0){break;}}}
}int get_idx(int a, int p)//求质数的指数
{int res = 0;while (a){res += a / p;a /= p;}return res;
}vector<int>mul(vector<int>a, int b)//高精度乘法
{vector<int> res;int len = a.size();int t = 0;for (int i = 0;i < len;i ++ ){int a1 = a[i];res.push_back((a1 * b + t) % 10);t = (a1 * b + t) / 10;}while (t){res.push_back(t % 10);t /= 10;}return res;
}int main()
{int a, b;cin >> a >> b;get_primes(a);for (int i = 0; i < cnt; i ++ ){int p = primes[i];idx[i] = get_idx(a, p) - get_idx(b, p) - get_idx(a - b, p);//C(a,b) = a!/b!/(a-b)! 所以要用a! - b! - (a - b)!,才能算出C(a,b)整体分解质因数后每个质数的指数是多少.}vector<int>res;res.push_back(1);for (int i = 0; i <= cnt;i ++ )//代入高精度乘法{for (int j = 0; j < idx[i]; j ++ ){res = mul(res, primes[i]);}}for(int i = res.size() - 1; i >= 0; i --)//高精度乘法：倒序存储，逆序输出{cout << res[i];}return 0;
}

题目五 卡特兰数

解题思路

原解题链接：https://www.acwing.com/solution/content/8907/

具体步骤：

1. 按照定义求卡特兰数；
2. 用快速幂求组合数中的逆元（模数为质数，可用费马小定理+快速幂求逆元);
3. 再求出卡特兰数中n+1的逆元即可；

代码实现

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;
const int M = 1e9 + 7;int qmi(int a, int b, int m)//快速幂求逆元
{int res = 1;while (b){if (b & 1){res = (LL)res * a % m;}b >>= 1;a = (LL)a * a % m;}return res;
}int main()
{int n;cin >> n;int a = 2 * n, b = n, res = 1;for (int i = a, j = 1; j <= b; j ++ , i -- )//按定义求组合数{res = (LL)res * i % M * qmi(j, M - 2, M) % M;}res = (LL)res * qmi(n + 1, M - 2, M) % M;cout << res;return 0;
}