这份题单主要介绍了一些在数数题里广泛应用的基础技术,主要受众是从未接触过生成函数数数题的同学。
当然,首先你需要一些生成函数知识。推荐我的【x义x讲坛】生成函数入门。
可能需要一些(多项式 Exp 板子,多项式开根板子,分治 FFT,MTT,牛顿迭代法)多项式基础知识。如果没有学过,推荐 神 Karry 的多项式题单。
不一定按难度排序。
题目(大多)选自我的【x义x讲坛】生成函数再入门。题解在这篇文章里(大多)都有。不过尽量自己思考一下吧。一道有趣的数数题如果不好好想一想就去看题解,那这题可以说就是被浪费了。
很适合作为开始接触生成函数的题目。了解一下生成函数计数的大致思想,以及 Exp 在计数问题中的现实意义。
简单的小练习。
简单的小练习。纯简单数学推导即可,也不需要多项式技术。
了解容斥和把式子化为卷积的技术。
了解利用 Ln 把卷积化为加法的技术。也可以使用 Euler 变换。
了解无标号图计数和 Euler 变换技术。了解分治 FFT 技术。
上上题的扩展练习。
应用练习。以及关于一个经典问题的 trick。
应用练习。
虽然不是生成函数计数问题,但是概率生成函数相关的知识也应该了解一下。不需要多项式技术。
概率生成函数的应用练习。
应用练习。前置知识:单位根反演,(和)Bluestein 算法(类似的思想)。
应用练习。很有趣(迫真)的题目。涉及大量知识点。
好像有个从高斯消元出发的神秘做法但我不会……
吾生也有涯,数数之毒瘤也无涯,我只能帮各位到这了……