|
前言：组合数在高中大家应该都学过，也是一个重要的数学知识，希望大家能够完全掌握
一、组合数基本知识
定义：
组合是数学的重要概念之一。从 n 个不同元素中每次取出 m 个不同元素 ，不管其顺序合成一组，称为从 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组合的种数称为组合数。
计算公式：
在线性写法中被写作C(n,m)。 组合数的计算公式为
n 元集合 A 中不重复地抽取 m 个元素作成的一个组合实质上是 A 的一个 m 元子集合。如果给集 A 编序 成为一个序集，那么 A 中抽取 m 个元素的一个组合对应于数段 到序集 A 的一个确定的严格保序映射。组合数 的常用符号还有
实际上是自然数集上的二元运算，这种运算既不满足交换律也不满足结合律。
性质：
互补性质
组合数基本公式 即从n个不同元素中取出m个元素的组合数=从n个不同元素中取出 (n-m) 个元素的组合数； 这个性质很容易理解，例如C(9,2)=C(9,7)，即从9个元素里选择2个元素的方法与从9个元素里选择7个元素的方法是相等的。 规定：C(n,0)=1 C(n,n)=1 C(0,0)=1 2.组合恒等式 若表示在 n 个物品中选取 m 个物品，则如存在下述公式：C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m)。
二、例题
1.组合数I
AC代码：
#include
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int C[N][N], T;
void init() {
for (int i = 0; i < N; ++ i) {
for (int j = 0; j >= 1;
}
return ans;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i < N; ++ i) {
fact[i] = (LL)fact[i - 1] * i % P;
infact[i] = (LL)infact[i - 1] * qmi(i, P - 2) % P;
}
}
int main()
{
init();
scanf("%d", &T);
while (T -- ) {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", (LL)fact[n] * infact[m] % P * infact[n - m] % P);
}
return 0;
}
3、组合数III
AC代码：
#include
using namespace std;
using LL = long long ;
int T, P;
int qmi(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (LL)ans * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return ans;
}
// 递推求解朴素的C(a,b)
int C(int n, int m) {
if (m > n) return 0;
int ans = 1;
// i控制的是分母的循环,对于b!，从1到b总共有b个数
// j控制的是分子的循环,从a到a-b+1总共有b个数
// 因此可以发现，分子和分母循环的次数是相同的
for (int i = 1, j = n; i >= 1;
}
return ans;
}
int main() {
scanf("%d", &n);
int a = 2 * n, b = n, ans = 1;
for (int i = 1, j = a; i |