【数学】生成函数基础
题单介绍
## 前言
这份题单主要介绍了一些在数数题里广泛应用的基础技术，主要受众是从未接触过生成函数数数题的同学。
当然，首先你需要一些生成函数知识。推荐我的[【x义x讲坛】生成函数入门](https://www.luogu.com.cn/blog/zyxxs/x-yi-x-jiang-tan-sheng-cheng-han-shuo-ru-men)。
可能需要一些（多项式 Exp 板子，多项式开根板子，分治 FFT，MTT，牛顿迭代法）多项式基础知识。如果没有学过，推荐 [神 Karry 的多项式题单](https://www.luogu.com.cn/training/1008)。
不一定按难度排序。
题目（大多）选自我的[【x义x讲坛】生成函数再入门](https://www.luogu.com.cn/blog/zyxxs/x-yi-x-jiang-tan-sheng-cheng-han-shuo-zai-ru-men)。题解在这篇文章里（大多）都有。不过尽量自己思考一下吧。一道有趣的数数题如果不好好想一想就去看题解，那这题可以说就是被浪费了。
## 题目列表
### [P4841 [集训队作业2013]城市规划](https://www.luogu.com.cn/problem/P4841)
> 很适合作为开始接触生成函数的题目。了解一下生成函数计数的大致思想，以及 Exp 在计数问题中的现实意义。
### [CF438E The Child and Binary Tree](https://www.luogu.com.cn/problem/CF438E)
> 简单的小练习。
### [P4451 [国家集训队]整数的lqp拆分](https://www.luogu.com.cn/problem/P4451)
> 简单的小练习。纯简单数学推导即可，也不需要多项式技术。
### [P4491 [HAOI2018]染色](https://www.luogu.com.cn/problem/P4491)
> 了解容斥和把式子化为卷积的技术。
### [P4389 付公主的背包](https://www.luogu.com.cn/problem/P4389)
> 了解利用 Ln 把卷积化为加法的技术。也可以使用 Euler 变换。
### [P5900 无标号无根树计数](https://www.luogu.com.cn/problem/P5900)
> 了解无标号图计数和 Euler 变换技术。了解分治 FFT 技术。
### [P3784 [SDOI2017]遗忘的集合](https://www.luogu.com.cn/problem/P3784)
> 上上题的扩展练习。
### [P4705 玩游戏](https://www.luogu.com.cn/problem/P4705)
> 应用练习。以及关于一个经典问题的 trick。
### [P5401 [CTS2019]珍珠](https://www.luogu.com.cn/problem/P5401)
> 应用练习。
### [P4548 [CTSC2006]歌唱王国](https://www.luogu.com.cn/problem/P4548)
> 虽然不是生成函数计数问题，但是概率生成函数相关的知识也应该了解一下。不需要多项式技术。
### [P3706 [SDOI2017]硬币游戏](https://www.luogu.com.cn/problem/P3706)
> 概率生成函数的应用练习。
### [P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/problem/P5293)
> 应用练习。前置知识：单位根反演，（和）Bluestein 算法（类似的思想）。
### [P5206 [WC2019] 数树](https://www.luogu.com.cn/problem/P5206)
> 应用练习。很有趣（迫真）的题目。涉及大量知识点。
### [P5326 [ZJOI2019]开关](https://www.luogu.com.cn/problem/P5326)
> 好像有个从高斯消元出发的神秘做法但我不会……
## 后记
吾生也有涯，数数之毒瘤也无涯，我只能帮各位到这了……