本题单仅考虑 OGF & EGF 及其衍生物。
本题单尝试抛开对多项式基础的讨论(意味着我编写题单时并不考虑你对多项式操作的掌握如何),尽量仅从生成函数角度评判难度和精简题目。
多种计数可能会根据难度综合排序,包括 Prufer 计数有根树计数有标号和无标号计数等等。
并不保证每种技巧都会有简单题。
以下很多题都可能存在不借助生成函数的推导方法,此处不过度讨论。
参考了许多前人的总结和我自己的理解,此处不再一一列出。
不过题单的初版来自 command_block 的「多项式计数杂谈」中,由我自己再扩展并尽量按难度简要排序。
以下是偷懒的部分做法采样。
这一部分应该是生成函数中最基础也是与 OI 中所用到的生成函数主要部分差距最大的部分。
它们通常不会具有强烈的组合意义,而是把重心放在线性递推通项的求解。
当然这部分题目多半也可以使用其他数列技巧解决。
简单贴几个题,以及还是得结合一点点其他技巧。
结合简单的根号分治预处理幂,俗称「光速幂」。
结合扩域技巧和斯特林数对下降幂的展开。
这里涉及到的无标号同构树计数都是二叉,因为更高叉数就需要涉及群论知识或者 Euler 变换(Polya Exp)。
而有标号计数或者仅要求儿子不同的树计数在此处就相对简单一些。
类卡特兰数的推导过程,通项公式上的关系也可以用组合意义解释。
在卡特兰数的生成函数中作复合。
写出生成函数的方程并不难,需要用到拉格朗日反演求解系数的通项。
这里包括在图计数中间插入奇怪的限制或者利用 Prufer 序列对树计数。
经典老番,不必多说。
简单考察 Prufer 序列的应用。其实真正有趣的图计数成分比较小。
考察一点点图论知识。
这里有根树不止包含「有根树」,也可能包含其他有根的东西。
通过枚举重心转化为有根树计数,然后对子树应用 Euler 变换。
钦定一个根便于分析问题。
类似地钦定根。需要运用拉格朗日反演。
考虑 DAG 上类似「根」的概念。
它还是来了。
需要对无标号计数有比较深的理解才能使用生成函数进行推导此题。
这部分的图计数多半需要考虑一些奇妙的性质来解决问题,而不像前一类中可以试图寻找根尝试划分问题。
当然由于没有固定套路,此类题目也比较少。
相对而言并不是十分困难。
对二分图的性质进行了一定的考察。
略为精妙且难以发现的性质,初见或许无从下手。
以下的计数不再在组合意义上具有鲜明的分类,故转为从代数层面进行分类。
插入一点小 trick 放松身心。
生成函数容易直接得到,然后利用 ODE 求得递推式。
利用 ODE 可以得到近线性的做法。
卡哥特色,科技推广。
如果只想要了解这个技巧的话,可以只做第一道。
这里包括一些不太方便直接在生成函数层面进行推导的题目。
还是迟早得面对的。
对了,卡哥非常喜欢。
从简单 DP 式到简单的生成函数,和斯特林数也有着一点点关系。
有趣的 DP 和可能有趣的微分方程。
生成函数意义上,综合性比较强的题目。
暂时好像只找到一道题可以归类进来。
说句闲话:膜拜 EI 和 xtq 的最好方式是……
从生成函数层面推导的话,需要事先深入理解欧拉数的生成函数,尽管如此也还是十分困难。
在我查找题目的过程中,逐渐意识到洛谷的生成函数题目还是比较局限,而科技却在一日日变迁。
我确实也可以理解生成函数之流进入公开赛、月赛甚至正式比赛确实会给在相关方面没有深入了解的选手造成困扰,但是自然有人出就得有人学,有人学就得有人领导。
最后引用一句 EI 用过的签名。
江山代有才人出 各领风骚数百年
欢迎收看「浅谈多项式复合和拉格朗日反演」,与这个题单相对地,重在如何处理得到的生成函数。