加法原理
若完成一件事的方法有 类,其中第 类的方法包括 中不同的方法,且这些方式互不重合,则完成这件事共有 种不同的方法。
乘法原理
若完成一件事的方法有 个步骤,其中第 步骤有 中不同的完成方法,且这些步骤互不干扰,则完成这件事共有 种不同的方法。
排列数
从 个不同的元素中依次取出 个元素排成一列,产生的不同排列方法的数量是:
组合数
从 个不同的元素中依次取出 个元素组成一个集合(不考虑顺序),产生的不同集合数量是:
性质
Lucas 定理
若 是质数,则对应任意整数 , 有
二项式定理
证明
数学归纳法。当 时, 成立
假设当 时成立,则当 时有:
证毕。
裸题:计算系数。
多重集的排列数
多重集是指包含重复元素的广义集合。设 是由 个 , 个 个 组成的多重集,记。 的全排列数量为:
多重集的组合数
设 是由 个 , 个 个 组成的多重集,设 。从 中取出 个元素组成一个多重集(不考虑元素顺序),产生的多重集数量为
抽屉原理
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有 个元素放到 个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理
母函数
生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。
生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多。
形式上说,普通型生成函数用于解决多重集的组合问题,而指数型母函数用于解决多重集的排列问题。
母函数还可以解决递归数列的通项问题(例如使用母函数解决斐波那契数列的通项公式)。
Ignatius and the Princess III
Algorithm 1
考虑暴力递归
#include <bits/stdc++.h>
using namespace std;
int N;
int Solve(int N , int M) { //将 n 划分为 最大数不超过 m 的划分数
if(N == 1 || M == 1) return 1;
else if(N < M) return Solve(N , N);
else if(N == M) return 1 + Solve(N , N - 1);
else return Solve(N - M , M) + Solve(N , M - 1);
}
int main() {
while(~scanf("%d" ,&N)) {
printf("%d\n" ,Solve(N , N));
}
return 0;
}
时间复杂度
Algorithm 2
为了减少计算冗余,我们考虑
#include <bits/stdc++.h>
using namespace std;
int Dp[210][210] , n;
int main() {
for(int N = 1; N <= 200; N++) {
for(int M = 1; M <= 200; M++) {
if((N == 1) || (M == 1)) Dp[N][M] = 1;
else if(N < M) Dp[N][M] = Dp[N][N];
else if(N == M) Dp[N][M] = Dp[N][M - 1] + 1;
else Dp[N][M] = Dp[N][M - 1] + Dp[N - M][M];
}
}
while(~scanf("%d" ,&n)) {
printf("%d\n" ,Dp[n][n]);
}
return 0;
}
时间复杂度
Algorithm 3
重点:普通型母函数
本题实际上是回到形式幂级数的模板题
我们先用一个简单的栗子展开
从数字 中取出一个或多个相加(每个数最多只能用一次),能组成几个数?每个数有几种组合?
我们给出一个公式:
公式左边的 的幂与组合用到的数字 相对应,观察公式左边,包括四个部分, 中的 是 次幂, 中的 是 次幂,以此类推,刚好是数字
-
公式右边 的幂与表格中的组合数 是对应的。公式右边的 的幂从 到 , 组合数也是 到
-
公式右边的系数与表格中的 相对应,都是 。
因此,用这个公式可以计算上面的组合数问题.
这就是回到形式幂级数的原理:把组合问题的加法与幂级数的乘幂对应起来
解释这个公式也很简单,为了理解,我们将公式写为:
其含义以 为例, 表示用 个 , 表示用 个 。
所以,这个公式的本质就是组合问题的反应:用或者不用数字 ,用或者不用数字 ,以此类推,公式就是这样构造出来的。
回到本题,母函数显然为:
暴力展开多项式即可
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
int Ans[MAXN] , C[MAXN];
int S;
void Solve() {
for(int i = 0; i <= 200; i++) {
Ans[i] = 1;
}
for(int k = 2; k <= 200; k++) {
for(int i = 0; i <= 200; i++) {
for(int j = 0; j + i <= 200; j += k) {
C[i + j] += Ans[i];
}
}
for(int i = 0; i <= 200; i++) {
Ans[i] = C[i];
C[i] = 0;
}
}
}
int main() {
Solve();
while(~scanf("%d" ,&S)) {
printf("%d\n" ,Ans[S]);
}
return 0;
}
时间复杂度:
既然DP的时间复杂度更优,为什么要用生成函数
优点:容易想、空间小(强行挽回颜面
普通型母函数
定义:
对于任意数列
即用如下方法与一个函数联系起来:
则称 是数列的生成函数
其一般形式为:
求斐波那契数列通项
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:在数学上,斐波那契数列以如下被以递推的方法定义:,,——百度百
我们设
考虑到这是封闭形式,我们尝试用待定系数法将其化为广义二项式的形式并将其展开。
设:
然后进行通分
解得:
那么:
所以我们就得到了斐波那契数列的通项公式:
注:
回到形式幂级数
见上
指数型母函数
排列组合
分析题目,假设有 种 物品 , 数量分别为 ,即 ,任选两件物品,则排列是 ,共 种。
针对这个例子,直接给出指数型母函数的解法,我相信你们一定能够理解
公式的最后一行隐藏了答案,例如 , 的幂 表示选 个物品,其系数(此处指分母上方) 表示有 种排列。
公式分析:公式写成 的形式,实际上是在处理排列 (要是这都理解不了,排列组合白学了)
为了更容易理解,以可以写成
+,不选 的排列有 种,即
+,选一件 的排列有 种,即
+ ,选两件 的排列有 种,即
本题代码与回到形式幂级数相似,请自行编写,需要看的私信找我。
Catalan 数
给定 个 和 个 ,它们按照某种序列排成长度为 的序列,满足任意前缀 的个数都不少于 的个数,序列的数量有:
Catalan数的公式,生成函数刚讲完,自行推导吧
均摊 的解法
设 表示 卡特兰数的第 项,由公式,得 ,同理,设 表示卡特兰数的第 项,即为
设: