2020-2021:teams:looking_up_at_the_starry_sky:生成函数
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:looking_up_at_the_starry_sky:生成函数 [2020/05/31 20:33] 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 排列组合'' | ||
| + | |||
| ====== 生成函数 ====== | ====== 生成函数 ====== | ||
| - | **这几周比较忙，还有很多写得不详细的地方。\\ | + | 这几周比较忙，还有很多写得不详细的地方。\\ |
| + | |||
| + | 本文的知识点和例题可能比较片面。\\ | ||
| - | 本文的知识点和例题可能比较片面。**\\ | + | 参考了很多其他人写的，还没来得及写参考文献。 |
| === 形式幂级数 === | === 形式幂级数 === | ||
| 行 143: | 行 154: | ||
| $$ 依次取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 |
| $$ | $$ | ||
| 行 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/生成函数.1590928433.txt.gz · 最后更改: 2020/05/31 20:33 由 zzy
