2020-2021:teams:no_morning_training:shaco:知识点:数论:生成函数
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数论:生成函数 [2020/05/27 23:01] shaco 创建 |
2020-2021:teams:no_morning_training:shaco:知识点:数论:生成函数 [2020/05/28 08:34] (当前版本) shaco |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| 对于数列$a_{n}=\{a_1,a_2,···,a_n\}$，它的生成函数即为$f(x)={a_1x+a_2x^2+···+a_nx^n}$。 | 对于数列$a_{n}=\{a_1,a_2,···,a_n\}$，它的生成函数即为$f(x)={a_1x+a_2x^2+···+a_nx^n}$。 | ||
| ===== 常见类型 ==== | ===== 常见类型 ==== | ||
| - | \[{1+x^k+x^{2k}+···}\to\frac{1}{1-x^k}\] | + | 这里介绍的是一种将x限定在''(-1,1)''的范围内化简的结果（x本身也没有意义，可以添加一些设定），这样的简化结果利于后面的计算，而且与不化简的记过表达的意义是相同的。 |
| - | \[{1+x^k+x^{2k}+···+x^{nk}}\to\frac{1-x^{(n+1)k}}{1-x^k}\] | + | \[\sum_{i=0}^{\infty}{x^{ik}}=\frac{1}{1-x^k}\] |
| + | \[\sum_{i=0}^{n}{x^{ik}}=\frac{1-x^{(n+1)k}}{1-x^k}\] | ||
| + | \[\sum_{i=0}^{\infty}{C_{i+k-1}^{k-1}}{x^i}=\frac{1}{(1-x)^k}\] | ||
| + | ====== 解决问题 ===== | ||
| + | 将取不同物品的方案的生成函数相乘，得到的函数中$x^i$的系数即是共取i个物品的方案数。\\ | ||
| + | 通常通过化简约分的方式得到一个形状比较好的化简的生成函数，再将其还原为数列的表达方式，通过组合数学的方法计算系数。 | ||
| + | 看一个例子 | ||
| + | 我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。 | ||
| + | 苹果的生成函数是$\frac{1}{1-x^2}$，香蕉的生成函数是$\frac{1}{1-x^5}$，橘子的生成函数是$\frac{1-x^5}{1-x}$，梨的生成函数是$(1+x)$。\\ | ||
| + | 将它们相乘得到$\frac{1}{(1-x)^2}$，即为$1+2x+3x^2+···$，因此取''n''个水果的方案数就是''n+1''。 | ||
| + | ====== 例题 ===== | ||
| + | 先贴一个吧 | ||
| + | [[https://www.luogu.com.cn/problem/P2000|洛谷p2000 拯救世界]] | ||
2020-2021/teams/no_morning_training/shaco/知识点/数论/生成函数.1590591668.txt.gz · 最后更改: 2020/05/27 23:01 由 shaco
