文章目录
前言
一、组合数
二、例题，代码
AcWing 885. 求组合数 I
本题解析
AC代码
AcWing 886. 求组合数 II
本题解析
AC代码
AcWing 887. 求组合数 III
本题解析
AC代码
AcWing 888. 求组合数 IV
本题解析
AC代码
AcWing 889. 满足条件的01序列
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：求组合数，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、组合数
二、例题，代码
AcWing 885. 求组合数 I
本题链接：AcWing 885. 求组合数 I
本博客提供本题截图：
本题解析
AC代码
#include <iostream> using namespace std; const int N = 2010; const int INF = 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 - 1] + c[i - 1][j]) % INF; } int main() { init(); int n; cin >> n; while (n -- ) { int a, b; cin >> a >> b; cout << c[a][b] << endl; } return 0; }
AcWing 886. 求组合数 II
本题链接：AcWing 886. 求组合数 II
本博客提供本题截图：
本题解析
我们知道直接进行除法的话会有精度问题，所以我们可以用逆元去求解，关于逆元的求法见：数学知识：快速幂
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010, mod = 1e9 + 7; int fact[N], infact[N]; 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 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] * qmi(i, mod - 2, mod) % mod; } int n; scanf("%d", &n); while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod); } return 0; }
