组合计数
组合计数属于离散数学中的内容，离散数学主要研究的是离散对象。组合计数就是研究计算满足一定条件的离散对象安置方式。
前置知识
加法原理
完成一件事情有n类方式，第一类方式中有种方法，第二类方式中有
种方法，…，第n类方式有
种方法，完成这件事情总共有
种方法。
例如：从武汉到上海有乘火车、飞机、轮船3种交通方式可供选择，而火车、飞机、轮船分别有个班次，那么从武汉到上海共有
种方式可以到达。
乘法原理
做一件事，完成它需要分成[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bkuQPyTN-1653570559461)(https://bkimg.cdn.bcebos.com/formula/561ce0d0c21ba2a257cc72a28956377b.svg)]个步骤，做第一步有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Aa3ApgfK-1653570559463)(https://bkimg.cdn.bcebos.com/formula/f514174c0f323d49e49f92b641257515.svg)]种不同方法，做第二步有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wtpx6cRQ-1653570559463)(https://bkimg.cdn.bcebos.com/formula/bfed19c3943adb74a78b2b68002872ab.svg)]种不同方法，……，做第[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5624WCRh-1653570559464)(https://bkimg.cdn.bcebos.com/formula/561ce0d0c21ba2a257cc72a28956377b.svg)]步有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KvAYZ114-1653570559464)(https://bkimg.cdn.bcebos.com/formula/f581b6c51b20d3fc04617d35c84ae9e6.svg)]种不同方法，那么完成这件事共有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XRbmQ1qh-1653570559465)(https://bkimg.cdn.bcebos.com/formula/3b55e846c872a87cecdc76257c230777.svg)] 种不同的方法。
排列数
一般地，从n个不同元素中取出 个元素，按照一定的顺序排成一列，叫做从
个元素中取出
个元素的一个排列
特别地，当时，这个排列被称作全排列，记作
证明：第一个数有种选择，第二个数有
种选择，…，第
个数有
种选择。
组合数
从个不同的元素中取出
个元素组成一个集合（不考虑顺序），产生不同集合数量为
证明：如果不考虑顺序，从个中选择
个总共有
种选择方法，但是如果考虑顺序的话，选择出来的这
个数总共又有
种排列方式，所以有
，所以
注意：在数学中，组合数也可以用
组合数性质
求解组合数（重点重点）
方法一 递推法（杨辉三角法）
利用递推求解组合数，适用于不大的情况
借助性质，利用递推求组合数，时间复杂度
int C[10][10];
void Init() {
for (int i = 0; i < 10; 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];
}
}
} //此时C[n][m]就是Cnm
方法二 公式法（题目要求模p）
一般组合数的的结果非常大，题目常常要求取模后输出，可以直接利用公式计算。首先计算 ，因为除法无法直接取模，所以需要计算出
的逆元，然后将二者相乘，求得
。
逆元计算方法
- 当p不为质数但b,p互质时，利用扩展欧几里得求解逆元。
- 当p为质数时，可以直接利用费马小定理求逆元。
#include<iostream>
using namespace std;
int n,m,p;
long long pow(long long x,long long y)
{
if (y==0) return 1;
long long z=pow(x,y/2)%p;
if (y%2==0) return z*z%p;
return z*z%p*x%p;
}
long long ni(long long x,long long p)
{
return pow(x,p-2);//费马小定理求逆元
}
long long c(int n,int m,int p)
{
long long x=1,y=1;
for (int i=n;i>=n-m+1;i--) x=x*i%p;
for (int i=1;i<=m;i++) y=y*i%p;
return x*ni(y,p)%p;
}
int main()
{
cin>>n>>m>>p;
cout<<c(n,m,p);
}
方法三 预处理法（题目有多个询问）
当题目有多个询问组合数时，或者需要求许多不同的组合数时，可以先进行预处理，从而达到的回答组合数的值。
在计算阶乘的过程中，把 的每一个
的值何其逆元的值，存储在数组
与数组
中，预处理的时间复杂度是
，则
方法四 质因数分解法（要求进行高精运算）
当题目要求不取模，精确的算出的值，为了避免取模，可以将分子分母进行质因数分解，快速分解
的方法可以参照蓝书P138阶乘分解的题目，在数组中存储每个质因数的指数，并将分子，分母的质因数指数相减，最后把剩余质因子用高精度乘起来即可。
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;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) // 求n！中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= 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;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
get_primes(a); // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数
{
int p = primes[i];
高中数学：排列组合21种解题方法总结 sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);
单纯组合数题型
排列数与组合数进阶
一、二项式定理
例题：
直接利用二项式定理计算即可
二、多重集排列数
三、容斥
四、错位排列
问题模型：有个信封有
封信，如果这
封信都装在不同的信封里，问总共有多少种方法？
我们考虑两种情况：
- 前面
个信封全部装错
- 前面
我们另表示
封信全部装错的方法数。
考虑第一种情况：如果前面个信封全部装错，那么第
封信跟前面的任意一个交换都可以构成一个新的排列，总共有
种排列。
考虑第二种情况：前面个信封有一个没有装错，其余全部装错，那么第
封信只能跟那一个没有装错信封的信交换才能构成一个新的排列。前面
封信中每一封都可以没有装错所以有
种可能，剩余的
封都是装错的，总共有
种方法。
所以两种情况加起来总共有种方法。
我们为什么只考虑这两种情况，因为除这两种情况之外的其他情况都不能通过一次操作变成一个长度为的错牌
五、卡特兰数
卡特兰数是组合数学中一个常出现于各种计数问题中的数列。其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
换句话说，如果你在做题时，手动模拟，发现是这样一串数时，就可以往卡特兰数上考虑。
个
和
个
，通过一系列的组合，组成一个长度为
的序列，满足任意前缀中0的个数都不少于1的个数的序列数量为
卡特兰数经典问题
1.火车进出栈问题
题目描述
个元素进栈序列为：
，则有多少种出栈序列。
问题分析：
如果将入栈设为用代表，出栈用
代表，因为每个元素都要出栈，进栈，所以就有
个
，和
个
,而一个数只有先进栈才能出栈，所以这个问题就变成了，求
个
和
个
，通过一系列的组合，组成一个长度为
的序列，满足任意前缀中0的个数都不少于1的个数的序列数量为。请注意这个任意前缀就限定了在前缀中
肯定在1的前面。例如如果
，排列顺序为
，其前缀
和前缀
不满足0的个数都不少于1的个数，但当排序为
时，任意前缀均满足0的个数都不少于1的个数。所以就将该问题抽象成了卡特兰数问题。
2.括号问题
题目描述
个左括号与
个右括号所组成的合法括号序列的数量为
问题分析：
同理将左括号用表示，右括号用
表示，每个左括号需要匹配一个右括号，并且只有有一个左括号才会有一个右括号，这就又抽象成了
个
和
个
，通过一系列的组合，组成一个长度为
的序列，满足任意前缀中0的个数都不少于1的个数的序列数量，所以合法括号序列的数量为
3.二叉树问题
个节点构成的不同二叉树的数量为
这里的二叉树指的是满二叉树，及如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
问题分析：
因为是满二叉树，所以每一个节点必有一个左子树和一个右子树，对于具有 n（ n>1 ）个结点的二叉树来说，都可以看成是一个根结点、由$ i$ 个结点组成的左子树和由$ n-i-1$ 个结点组成的右子树。因为在生成二叉树时，先生成左子树，再生成右子树，将左子树中的节点设为，右子树中的节点设为
，而具有同一个父节点的左右节点是匹配的，这就与括号匹配和进出栈问题类似，所以可以用卡特兰数解决。
4.卡特兰数的几何意义
利用卡特兰数的几何意义解决问题： [SCOI2010]生成字符串
总结
卡特兰数问题中都会存在一种匹配关系，如进出栈匹配，括号匹配等，一旦计数问题中存在这种关系，那我们就需要去考虑这是否是卡特兰数问题。此外，我们还可以记住序列前四项：1, 1, 2, 5，这些将有利于我们联想到卡特兰数。
卡特兰数练习题
六、斯特林数（进阶内容）
题单：
文章出处登录后可见！
