生成函数之 OGF & EGF - 从入门到入土

## 前言 **本题单仅考虑 OGF & EGF 及其衍生物。** 本题单尝试抛开对多项式基础的讨论（意味着我编写题单时并不考虑你对多项式操作的掌握如何），**尽量**仅从生成函数角度评判难度和精简题目。 多种计数可能会根据难度综合排序，包括 Prufer 计数有根树计数有标号和无标号计数等等。 并不保证每种技巧都会有简单题。 以下很多题都可能存在不借助生成函数的推导方法，此处不过度讨论。 参考了许多前人的总结和我自己的理解，此处不再一一列出。 不过题单的初版来自 command_block 的「多项式计数杂谈」中，由我自己再扩展并**尽量**按难度简要排序。 以下是偷懒的部分做法采样。 ## I. 线性递推通项的推导 这一部分应该是生成函数中最基础也是与 OI 中所用到的生成函数主要部分差距最大的部分。 它们通常不会具有强烈的组合意义，而是把重心放在线性递推通项的求解。 当然这部分题目多半也可以使用其他数列技巧解决。 简单贴几个题，以及还是得结合一点点其他技巧。 ### P5110 块速递推 > 结合简单的根号分治预处理幂，俗称「光速幂」。 ### P5320 [BJOI2019]勘破神机 > 结合扩域技巧和斯特林数对下降幂的展开。 ## II. 类似卡特兰数的简单有根树计数 这里涉及到的无标号同构树计数都是二叉，因为更高叉数就需要涉及群论知识或者 Euler 变换（Polya Exp）。 而有标号计数或者仅要求儿子不同的树计数在此处就相对简单一些。 ### P3978 [TJOI2015]概率论 > 类卡特兰数的推导过程，通项公式上的关系也可以用组合意义解释。 ### CF438E The Child and Binary Tree > 在卡特兰数的生成函数中作复合。 ### P2767 树的数量 > 写出生成函数的方程并不难，需要用到拉格朗日反演求解系数的通项。 ## III. 一点简单的其他图计数 这里包括在图计数中间插入奇怪的限制或者利用 Prufer 序列对树计数。 ### P4841 [集训队作业2013]城市规划 > 经典老番，不必多说。 ### P5219 无聊的水题 I > 简单考察 Prufer 序列的应用。其实真正有趣的图计数成分比较小。 ### P4233 射命丸文的笔记 > 考察一点点图论知识。 ## IV. 进阶的有根树相关计数 这里有根树不止包含「有根树」，也可能包含其他有根的东西。 ### P5900 无标号无根树计数 > 通过枚举重心转化为有根树计数，然后对子树应用 Euler 变换。 ### P5434 有标号荒漠计数 > 钦定一个根便于分析问题。 ### P5828 边双连通图计数 & P5827 点双连通图计数 > 类似地钦定根。需要运用拉格朗日反演。 ### P6295 有标号 DAG 计数 > 考虑 DAG 上类似「根」的概念。 ### P4500 [ZJOI2018]树 > 它还是来了。 > 需要对无标号计数有比较深的理解才能使用生成函数进行推导此题。 ## V. 进阶的其他图计数 这部分的图计数多半需要考虑一些奇妙的性质来解决问题，而不像前一类中可以试图寻找根尝试划分问题。 当然由于没有固定套路，此类题目也比较少。 ### P6516 [QkOI#R1] Quark and Graph > 相对而言并不是十分困难。 ### P7364 有标号二分图计数 > 对二分图的性质进行了一定的考察。 ### P5448 [THUPC2018]好图计数 > 略为精妙且难以发现的性质，初见或许无从下手。 --- 以下的计数不再在组合意义上具有鲜明的分类，故转为从代数层面进行分类。 ## VI. 利用 ODE 对生成函数进行处理 插入一点小 trick 放松身心。 ### P4931 [MtOI2018]情侣？给我烧了！（加强版） > 生成函数容易直接得到，然后利用 ODE 求得递推式。 ### P5401 [CTS2019]珍珠 > 利用 ODE 可以得到近线性的做法。 ### P7438 & P7439 & P7440 「KrOI2021」Feux Follets 三连 > 卡哥特色，科技推广。 > 如果只想要了解这个技巧的话，可以只做第一道。 ## VII. 从 DP 式到生成函数 这里包括一些不太方便直接在生成函数层面进行推导的题目。 还是迟早得面对的。 对了，卡哥非常喜欢。 ### P7435 简单的排列计数 > 从简单 DP 式到简单的生成函数，和斯特林数也有着一点点关系。 ### P7289 & P7292 「EZEC-5」「KrOI2021」Chasse Neige 二连 > 有趣的 DP 和可能有趣的微分方程。 ## VIII. 最终魔王 生成函数意义上，综合性比较强的题目。 暂时好像只找到一道题可以归类进来。 ### CF1349F1 & CF1349F2 Slime and Sequences > 说句闲话：膜拜 EI 和 xtq 的最好方式是…… > 从生成函数层面推导的话，需要事先深入理解欧拉数的生成函数，尽管如此也还是十分困难。 ## 后记 在我查找题目的过程中，逐渐意识到洛谷的生成函数题目还是比较局限，而科技却在一日日变迁。 我确实也可以理解生成函数之流进入公开赛、月赛甚至正式比赛确实会给在相关方面没有深入了解的选手造成困扰，但是自然有人出就得有人学，有人学就得有人领导。 最后引用一句 EI 用过的签名。 > 江山代有才人出 各领风骚数百年 ## 广告 欢迎收看[「浅谈多项式复合和拉格朗日反演」](https://www.luogu.com.cn/blog/your-alpha1022/qian-tan-duo-xiang-shi-fu-ge-hu-la-ge-lang-ri-fan-yan)，与这个题单相对地，重在如何处理得到的生成函数。