2020-2021:teams:looking_up_at_the_starry_sky:生成函数
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:looking_up_at_the_starry_sky:生成函数 [2020/05/31 20:21] zzy |
2020-2021:teams:looking_up_at_the_starry_sky:生成函数 [2020/06/12 18:56] (当前版本) admin del |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ==== 生成函数 ==== | + | **格式**： |
| + | - 标题按一级、二级依次排列，有些地方如例题中的''指数型生成函数''写成标题，便于检索 | ||
| + | - 公式两边接汉字请空格 | ||
| + | - $\%x^{n}\to\bmod x^{n}$ | ||
| - | **这几周比较忙，还有很多写得不详细的地方。\\ | + | **内容**： |
| + | - 题目讲得太难了吧，从基础开始循序渐进，在定义和难题之间应该有一些基本应用及简单题 | ||
| + | - 出现了一些 typo，如 ''HUD 排列组合'' | ||
| - | 可能对于整个生成函数来说，本文的知识点和例题比较片面。\\ | + | ====== 生成函数 ====== |
| + | |||
| + | 这几周比较忙，还有很多写得不详细的地方。\\ | ||
| + | |||
| + | 本文的知识点和例题可能比较片面。\\ | ||
| + | |||
| + | 参考了很多其他人写的，还没来得及写参考文献。 | ||
| === 形式幂级数 === | === 形式幂级数 === | ||
| 行 93: | 行 104: | ||
| 用$a_i$表示$i$这个元素是否为集合中的元素。 | 用$a_i$表示$i$这个元素是否为集合中的元素。 | ||
| - | 则整个集合种元素的生成函数 $$ | + | 则整个集合中元素的生成函数 $$ |
| F(x)=\prod_{i=1}^{n}\left(\frac{1}{1-x^i}\right)^{a_i} | F(x)=\prod_{i=1}^{n}\left(\frac{1}{1-x^i}\right)^{a_i} | ||
| $$ 与上一题同样可得 $$ | $$ 与上一题同样可得 $$ | ||
| 行 115: | 行 126: | ||
| $S_n^m$表示把n个不同的元素构成m个圆排列的方案数（不能有空的环） | $S_n^m$表示把n个不同的元素构成m个圆排列的方案数（不能有空的环） | ||
| - | $S_n(x)$表示第n列斯特林数的生成函数 $$ | + | $S_n(x)$表示第n行斯特林数的生成函数 $$ |
| - | S_n(x)=\sum_{i=0}^{\infin}S_n^i x^i | + | S_n(x)=\sum_{i=0}^{\infty}S_n^i x^i |
| $$ | $$ | ||
| 行 131: | 行 142: | ||
| $$ | $$ | ||
| - | 可以分治FFT，在$O(nlog^2n)$的复杂度内求出，大概也有$O(nlogn)$的求法。 | + | 可以分治FFT，在$O(nlog^2n)$的复杂度内求出，也有$O(nlogn)$的求法。 |
| [[https://www.luogu.com.cn/problem/P5409|第一类斯特林数·列]] | [[https://www.luogu.com.cn/problem/P5409|第一类斯特林数·列]] | ||
| 行 139: | 行 150: | ||
| 考虑n个有标号元素组成的环的方案数$(n-1)!$ | 考虑n个有标号元素组成的环的方案数$(n-1)!$ | ||
| - | 考虑取一个带标号环的方案数，可以表示为EGF $$ | + | 考虑取一个带标号环，可以表示为EGF $$ |
| \sum_{i \ge 1}(i-1)!\frac{x^i}{i!} | \sum_{i \ge 1}(i-1)!\frac{x^i}{i!} | ||
| $$ 依次取m个环，方案数$/m!$ $$ | $$ 依次取m个环，方案数$/m!$ $$ | ||
| F(x)=\frac{1}{m!}\left(\sum_{i \ge 1}(i-1)!\frac{x^i}{i!}\right)^m | F(x)=\frac{1}{m!}\left(\sum_{i \ge 1}(i-1)!\frac{x^i}{i!}\right)^m | ||
| - | $$ | ||
| - | |||
| - | $$ | ||
| - | S_n^m=n![x^n]F(x) | ||
| $$ | $$ | ||
| 行 165: | 行 172: | ||
| $S_m(x)$表示第m列斯特林数的生成函数 $$ | $S_m(x)$表示第m列斯特林数的生成函数 $$ | ||
| - | S_m(x)=\sum_{i=0}^{\infin}S_i^m x^i | + | S_m(x)=\sum_{i=0}^{\infty}S_i^m x^i |
| $$ | $$ | ||
| 行 180: | 行 187: | ||
| $$ | $$ | ||
| - | $\prod_{i=1}^{m}(1-ix)$可以分治FFT，在$O(nlog^2n)$的复杂度内求出，大概也有$O(nlogn)$的求法。 | + | $\prod_{i=1}^{m}(1-ix)$可以分治FFT，在$O(nlog^2n)$的复杂度内求出，也有$O(nlogn)$的求法。 |
| 2020牛客寒假算法基础集训营4 [[https://ac.nowcoder.com/acm/contest/3005/J|二维跑步]] | 2020牛客寒假算法基础集训营4 [[https://ac.nowcoder.com/acm/contest/3005/J|二维跑步]] | ||
| 行 206: | 行 213: | ||
| 用RBGY四种颜色涂满长度为n的序列，RG这两种颜色需要出现偶数次。 | 用RBGY四种颜色涂满长度为n的序列，RG这两种颜色需要出现偶数次。 | ||
| - | 这是一个带标号组合问题，标号可以理解为这个某个颜色的位置。 | + | 这是一个带标号组合问题，标号可以理解为颜色的位置。 |
| 考虑R，涂满长度为 0~n的序列的方案数为 1，0，1，0，1，0，1，0，1… | 考虑R，涂满长度为 0~n的序列的方案数为 1，0，1，0，1，0，1，0，1… | ||
| 行 222: | 行 229: | ||
| \\ | \\ | ||
| =\frac{1}{4}+\frac{1}{4}\sum_{i \ge 0}\frac{4^i+2^{i+1}}{i!}x^i | =\frac{1}{4}+\frac{1}{4}\sum_{i \ge 0}\frac{4^i+2^{i+1}}{i!}x^i | ||
| - | $$ $n \ge 1$时， $x^n[x^n]F(x)=4^{n-1}+2^{n-1}$可以用快速幂求出。 | + | $$ $n \ge 1$时， $n![x^n]F(x)=4^{n-1}+2^{n-1}$可以用快速幂求出。 |
| - | 或者 $f[i][j](0 \le j \le 3)$表示dp到第i个位置，RG分别放了奇数次/偶数次得方案数，可以矩阵快速幂优化。 | + | 或者 $f[i][j](0 \le j \le 3)$表示dp到第i个位置，RG分别放了奇数次/偶数次的方案数，可以矩阵快速幂优化。 |
| [[http://acm.hdu.edu.cn/showproblem.php?pid=1521|HUD 排列组合]] | [[http://acm.hdu.edu.cn/showproblem.php?pid=1521|HUD 排列组合]] | ||
| - | 有n种物品，并且知道每种物品的数量 $a_i$ 。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有“AB”,“BA”两种。$n,m(1 \le m,n \le10)$ | + | 有n种物品，并且知道每种物品的数量 $a_i$ 。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有“AB”,“BA”两种。$(1 \le m,n \le10)$ |
| 这是一个带标号组合问题，标号可以理解为某个物品的位置。 | 这是一个带标号组合问题，标号可以理解为某个物品的位置。 | ||
| 第i个物品的EGF $$ | 第i个物品的EGF $$ | ||
| - | \sum_{i=0}^{a_i}\frac{1}{i!}x^i | + | \sum_{i=0}^{a_i}\frac{x^i}{i!} |
| $$ 将n个物品的EGF乘起来得$F(x)$ ，则答案为 $$ | $$ 将n个物品的EGF乘起来得$F(x)$ ，则答案为 $$ | ||
| m! [x^m]F(x) | m! [x^m]F(x) | ||
2020-2021/teams/looking_up_at_the_starry_sky/生成函数.1590927669.txt.gz · 最后更改: 2020/05/31 20:21 由 zzy
