洒水车生成函数/计数练习 #19 ~ #21

“洒水车” SamShawCraft 在 Bilibilii 上第十九期、第二十期、二十一期信息学竞赛半月刊讲解时使用的题单。题目主要涉及生成函数（OGF,EGF）。本题单题目编排大量参考现有的题单，但是题目顺序未必从易到难安排，请根据信息学竞赛半月刊视频内容和自己的能力水平确定做题顺序。 #### 主要内容 - 生成函数基础 - 推式子技巧 - 卡常技巧 - OGF,EGF - OGF 解决的是组合问题（无标号），EGF 解决的是排列问题（有标号）。 - PGF 推式子，套结论 - 常见计数问题与常见计数思路 - 无根图计数转化为有根图计数 - 序列问题（有序）转化为集合问题（无序） - 和度数有关的树计数问题转换为 Prüfer 序列问题 - 恰好问题转化为至少问题 - 递推公式推出生成函数 - 整体问题转化为组成部分问题 - 改变式子枚举顺序或枚举对象 - 正难则反 #### 非洛谷题目 LibreOJ [tag:生成函数/母函数](https://loj.ac/p?tagIds=143) #### 前置知识 即使没有学习过标 `*` 的知识也可以完成本题单。 - 经典微积分 - 最基本的函数的求导和积分会算即可。 - 多项式基本运算 - 快速傅里叶变换，快速数论变换，快速沃尔什变换 - 多项式乘法，含任意模数多项式乘法 polymul - 多项式求逆 polyinv - 多项式对数函数 polyln - 多项式指数函数 polyexp - 多项式幂函数 polypow - 多项式开平方根 polysqrt - 具体地说，这里的多项式开根不宜用多项式幂函数做，时间开销和码量大，建议使用多项式求逆和多项式乘法的做法。注意这一做法在老 Sam 的前十八期信息学竞赛半月刊中没有出现过，请参考 \#19 中多项式开根的做法。 - 多项式平移 polyoffset - 分治 FFT，分治 NTT - 高斯消元，拉格朗日插值，`*` 牛顿迭代法 - `*` Euler 变换，`*` Burnside 引理，`*` Pólya 定理 - Chirp Z-变换 - 特征方程，`*` 常系数齐次线性递推通项，矩阵快速幂 - 原根，二次剩余（`*` Cipolla 算法），`*` BSGS，`*` exBSGS - 根号分治，含光速幂等 - 基本组合计数，含二项式系数、卡特兰数、斯特林数等 - 莫比乌斯反演、二项式反演、拉格朗日反演等反演公式 - 概率与期望 - Prüfer 序列 #### 学习资料 链接排名不分先后，请按需学习。不排除在较长一段时间之后链接失效的可能，如果有链接失效请及时通过 Bilibili 或 QQ 联系本人，本人将补充类似学习资料并给失效的学习资料添加 tag。 - [OI-Wiki - 生成函数](https://oi-wiki.org/math/gen-func/intro/) - [RabbitHu - 趣谈生成函数](https://www.cnblogs.com/RabbitHu/p/9178645.html) - [\_rqy - 浅谈 OI 中常用的一些生成函数运算的合法与正确性](https://www.luogu.com.cn/blog/lx-2003/gf-correct) - [\_rqy - 铃悬的数学小讲堂——生成函数初步](https://www.luogu.com.cn/blog/lx-2003/generating-function) - [\_rqy - 铃悬的数学小讲堂——生成函数进阶与简单的图计数](https://www.luogu.com.cn/blog/lx-2003/generating-function-advanced) - [x义x - 【x义x讲坛】生成函数入门](https://www.luogu.com.cn/blog/zyxxs/x-yi-x-jiang-tan-sheng-cheng-han-shuo-ru-men) - [x义x - 【x义x讲坛】生成函数再入门](https://www.luogu.com.cn/blog/zyxxs/x-yi-x-jiang-tan-sheng-cheng-han-shuo-zai-ru-men) - [Paulliant - 浅谈生成函数与组合计数，多项式全家桶（未完）](https://www.cnblogs.com/Paulliant/p/12054504.html) - [command_block - 多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan) - [command_block - 炫酷反演魔术](https://www.luogu.com.cn/blog/command-block/xuan-ku-fan-yan-mo-shu) - [command_block - 半在线卷积小记](https://www.luogu.com.cn/blog/command-block/ban-zai-xian-juan-ji-xiao-ji) - [command_block - 矩阵树定理(+行列式)](https://www.luogu.com.cn/blog/command-block/ju-zhen-shu-ding-li-xing-lie-shi-post) - [command_block - 斯特林数的四种求法](https://www.luogu.com.cn/blog/command-block/si-te-lin-shuo-zong-jie) - [Karry5307 - 浅谈欧拉数](https://www.luogu.com.cn/blog/Karry5307/eulerian-numbers) - [Dylaaan - 特征方程与特征根](https://zhuanlan.zhihu.com/p/104596563) - [HM Zhao - 数列、矩阵与微分方程的特征值](https://zhuanlan.zhihu.com/p/109529158) - [birchtree - 二项式反演学习笔记](https://www.cnblogs.com/birchtree/p/12811308.html) - [Luckyblock - 「笔记」斯特林数 及 斯特林反演 ](https://www.cnblogs.com/luckyblock/p/13424433.html) - [alpha1022 - 浅谈多项式复合和拉格朗日反演](https://www.luogu.com.cn/blog/your-alpha1022/qian-tan-duo-xiang-shi-fu-ge-hu-la-ge-lang-ri-fan-yan) - [SamShawCraft - 信息学竞赛半月刊 8月A刊 莫比乌斯反演入门知识与简单题解](https://www.bilibili.com/video/BV11L411n7Dd/) - [SamShawCraft - 信息学竞赛半月刊-12月B刊-生成函数/计数问题前置技巧与前18期月刊的勘误](https://www.bilibili.com/video/BV1SL4y1J7EE) - [SamShawCraft - 信息学竞赛半月刊-5月B刊-重探多项式的基础](https://www.bilibili.com/video/BV1H5411R75M/) - [SamShawCraft - 信息学竞赛半月刊-1月A刊-这绝对不是哔哩哔哩最全的生成函数题解集 Part I](https://www.bilibili.com/video/BV1XL4y1E7o1/) - [SamShawCraft - 信息学竞赛半月刊-2月A刊-这绝对不是哔哩哔哩最全的生成函数题解集 Part II](https://www.bilibili.com/video/BV1Mq4y1c7pT/)