组合数学入门知识点总结
题目来源:https://vjudge.net/contest/295931#overview
常见知识点:
常见公式:
来自于:https://blog.csdn.net/sdz20172133/article/details/81433159
A(n,r)=n(n-1)…(n-r+1)=n!/(n-r)!
C(n,r)=A(n,r)/r!=n!/((n-r)r!)
C(n,r)=C(n,n-r)
C(n,r)=C(n-1,r)+C(n-1,r-1)
C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)
C(n,k)C(k,r)=C(n,r)C(n-r,k-r)
C(n,k+1)=C(n,k)*(n-k)/(k+1)
重复排列:n^r;
可重复组合:C(n+r-1,r)
不相邻组合:C(n-r+1,r)
圆周排列:A(n,r)/r
项链排列:A(n,r)/2r
多重全排列(r1个a1,r2个a2……组成n位串):n!/(r1!r2!…)
母函数:
科普:
1.https://zh.wikipedia.org/zh-hans/母函数
2.更好理解:http://www.cnblogs.com/dolphin0520/archive/2012/11/07/2755080.html
理解:
普通母函数:从n个地方选取相同的东西的排列(不排序)
指数母函数:
从n个地方选取不同的东西的排列(排列)
题目:
普通母函数入门题:hdu2082 http://acm.hdu.edu.cn/showproblem.php?pid=2082
题解:https://blog.csdn.net/weixin_43331783/article/details/89388476
指数型母函数:
hdu1521 http://acm.hdu.edu.cn/showproblem.php?pid=1521
板刷普通母函数:
hdu1085 http://acm.hdu.edu.cn/showproblem.php?pid=1085
hdu1398 http://acm.hdu.edu.cn/showproblem.php?pid=1398
hdu1028 http://acm.hdu.edu.cn/showproblem.php?pid=1028
hdu2152 http://acm.hdu.edu.cn/showproblem.php?pid=2152
题解:https://blog.csdn.net/weixin_43331783/article/details/89889908
普通母函数稍微变化:
hdu1171 http://acm.hdu.edu.cn/showproblem.php?pid=1171
题解:https://blog.csdn.net/weixin_43331783/article/details/89765786
hdu2069 http://acm.hdu.edu.cn/showproblem.php?pid=2069
题解:https://blog.csdn.net/weixin_43331783/article/details/89855195
模板:
#include<bits/stdc++.h>
using namespace std;
const int maxn=?;
int c1[maxn+5],c2[maxn+5];
const int type=?;
int number[type],value[type];
int main() {
int n;
cin >> n;
while (n--) {
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
for (int i = 1; i <=type; i++)
cin >> number[i]>>value[i];
c1[0] = 1;
for (int i = 1; i <= type; i++) {
for (int j = 0; j <=maxn; j++)
for (int k = 0; k <= number[i] && j + k *value[i]<=maxn; k++) {
c2[j + k *value[i]] += c1[j];
}
memcpy(c1, c2, sizeof(c2));
memset(c2, 0, sizeof(c2));
}
int ans = 0;
for (int i = 1; i <= maxn; i++)ans += c1[i];
cout << ans << endl;
// 求总价值为maxn的方案cout<<c1[maxn]<<endl;
}
}
卡特兰数:
科普:
https://zh.wikipedia.org/wiki/
1-100的卡特兰数:http://blog.csdn.net/lttree/article/details/29392541
前十个:
1
2
5
14
42
132
429
1430
4862
16796
简单来讲卡特兰数就是
递推式cn=cn-1*(4*n-2)/(n+1);
应用题目:
具体看*,我的理解就是由两个相同数量的东西匹配而其中一个从前遍历一定比后面得多
1.栈的出入有多少的出去顺序。
2.dyck word数
3.合法运算式数
4.n个节点组成不同构二叉树的方案数
5.在n × n格点中不越过对角线的单调路径的个数
6.连结顶点而将n + 2边的凸多边形分成三角形的方法个数
7.Cn表示表为2×n的矩阵的标准杨氏矩阵的数量。 也就是说,它是数字 1, 2, …, 2n 被放置在一个2×n的矩形中并保证每行每列的数字升序排列的方案数。
例题:HDU - 1023 https://vjudge.net/contest/295931#problem/C
题解:https://blog.csdn.net/weixin_43331783/article/details/89399711
模板:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 105;
int a[MAXN][MAXN];
///可以作为模板
void Catalan()
{
int len=1,yushu=0;
a[1][0]=1;
a[1][1]=1;
for(int i=2/*1*/;i<MAXN;i++){
yushu=0;/**/
for(int j=1;j<=len;j++)
{
int k=a[i-1][j]*(4*i-2)+yushu;
a[i][j]=k%10;yushu=k/10;
}
while(yushu)
{a[i][++len]=yushu%10;
yushu/=10;}
for(int j=len;j>=1;j--)
{
int k=a[i][j]+yushu*10;
a[i][j]=k/(i+1)/*10*/;
yushu=k%(i+1);
}
while(!a[i][len])
len--;
a[i][0]=len;
}
}
int main()
{
Catalan();
int n;
while(cin>>n)
{
for(int i=a[n][0]; i>0; i--)
cout<<a[n][i];
cout<<endl;
}
return 0;
}
第一类斯特林数
科普:
https://zh.wikipedia.org/zh-hans/斯特林数
Stirling[n][k]
1
1 1
2 3 1
6 11 6 1
24 50 35 10 1
120 274 225 85 15 1
720 1764 1624 735 175 21 1
5040 13068 13132 6769 1960 322 28 1
40320 109584 118124 67284 22449 4536 546 36 1
362880 1026576 1172700 723680 269325 63273 9450 870 45 1
理解:
给n个元素,求出k个环排列的方法数
题目:
HDU - 4372 http://acm.hdu.edu.cn/showproblem.php?pid=4372
题解: https://blog.csdn.net/weixin_43331783/article/details/89482294
模板:
const int maxn = 21;
ll Stirling[maxn][maxn], fac[maxn] = {1};
void init() {
for(ll i = 1; i < maxn; i++)
fac[i] = fac[i - 1] * i;
Stirling[0][0] = 0;
Stirling[1][1] = 1;
for(ll i = 2; i < maxn; i++) {
for(ll j = 1; j <= i; j++) {
Stirling[i][j] = Stirling[i - 1][j - 1] + (i - 1) * Stirling[i - 1][j];
}
}
}
第二类斯特林数
科普:
https://zh.wikipedia.org/wiki/斯特林数
Stirling[n][m]
1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
1 63 301 350 140 21 1
1 127 966 1701 1050 266 28 1
1 255 3025 7770 6951 2646 462 36 1
1 511 9330 34105 42525 22827 5880 750 45 1
理解:
将n个不同元素拆分成m个集合的方案数
题目:
HDU - 4045 http://acm.hdu.edu.cn/showproblem.php?pid=4045
题解: https://blog.csdn.net/weixin_43331783/article/details/89647365
模板:
const int maxn = 21;
ll Stirling[maxn][maxn];
void init() {
Stirling[0][0] = 0;
Stirling[1][1] = 1;
for(ll i = 2; i < maxn; i++) {
for(ll j = 1; j <= i; j++) {
Stirling[i][j] = Stirling[i - 1][j - 1] + j * Stirling[i - 1][j];
}
}
}
贝尔数
科普:
https://zh.wikipedia.org/wiki/贝尔数
1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322,
用以下方法建构一个三角矩阵(形式类似杨辉三角形):
第一行第一项是1
对于n>1,第n行第一项等同第n-1行最后一项。
对于m,n>1,第n行第m项等于它左边和左上方的两个数之和。每行首项是贝尔数
理解:
n个数可以划分成多少个集合
每个贝尔数是第二类斯特林数的和
题目:
HDU - 2512 http://acm.hdu.edu.cn/showproblem.php?pid=2512
题解: https://blog.csdn.net/weixin_43331783/article/details/89856392
模板:
const int maxn = 21;
ll Bell[maxn];
void init() {
ll T[maxn];
Bell[0] = 1;
Bell[1] = 1;
T[0] = 1;
for(int i = 2; i < maxn; i++) {
T[i - 1] = Bell[i - 1];
for(int j = i - 2; j >= 0; j--)
T[j] = T[j] + T[j + 1];
Bell[i] = T[0];
}
}
斯特林数贝尔数参考https://blog.csdn.net/sxh759151483/article/details/83420939
其他组合数学题:
1.简单组合数学(回文求组合数思维)
HDU - 5651 http://acm.hdu.edu.cn/showproblem.php?pid=5651
https://blog.csdn.net/weixin_43331783/article/details/89366230
2.dp
HDU - 4248 http://acm.hdu.edu.cn/showproblem.php?pid=4248
https://blog.csdn.net/weixin_43331783/article/details/89478375
组合dp
HDU - 4532 http://acm.hdu.edu.cn/showproblem.php?pid=4532
https://blog.csdn.net/weixin_43331783/article/details/89683854
3.二进制拆分
HDU - 4810 https://vjudge.net/contest/295931#problem/L
https://blog.csdn.net/weixin_43331783/article/details/89763429
4.基础数论
HDU - 1124 http://acm.hdu.edu.cn/showproblem.php?pid=1124
https://blog.csdn.net/weixin_43331783/article/details/89526020
那罗延莫慈金数杨辉三角
默慈金数:
https://blog.csdn.net/WuBaizhe/article/details/80027591(很重要)
https://blog.csdn.net/linruier2017/article/details/81748835
https://blog.csdn.net/qingshui23/article/details/52068031(很重要)
http://www.voidcn.com/article/p-afdwxuvv-bqy.html
https://blog.csdn.net/bestsort/article/details/81185475
组合数学进阶:https://blog.csdn.net/sdz20172133/article/details/81432667
杨辉三角
斐波那契
https://zh.wikipedia.org/wiki/斐波那契数列
杨表
1-n填n个方格试得每行从左到右每列从下到上递增
特殊情况1-2n放在2Xn矩阵那方案数就是卡特兰数,感觉这个没什么乱用
上一篇: 【状态模式】—— 描述行为变化