【数学】生成函数基础

前言

这份题单主要介绍了一些在数数题里广泛应用的基础技术,主要受众是从未接触过生成函数数数题的同学。

当然,首先你需要一些生成函数知识。推荐我的【x义x讲坛】生成函数入门。

可能需要一些(多项式 Exp 板子,多项式开根板子,分治 FFT,MTT,牛顿迭代法)多项式基础知识。如果没有学过,推荐 神 Karry 的多项式题单。

不一定按难度排序。

题目(大多)选自我的【x义x讲坛】生成函数再入门。题解在这篇文章里(大多)都有。不过尽量自己思考一下吧。一道有趣的数数题如果不好好想一想就去看题解,那这题可以说就是被浪费了。

题目列表

P4841 [集训队作业2013]城市规划

很适合作为开始接触生成函数的题目。了解一下生成函数计数的大致思想,以及 Exp 在计数问题中的现实意义。

CF438E The Child and Binary Tree

简单的小练习。

P4451 [国家集训队]整数的lqp拆分

简单的小练习。纯简单数学推导即可,也不需要多项式技术。

P4491 [HAOI2018]染色

了解容斥和把式子化为卷积的技术。

P4389 付公主的背包

了解利用 Ln 把卷积化为加法的技术。也可以使用 Euler 变换。

P5900 无标号无根树计数

了解无标号图计数和 Euler 变换技术。了解分治 FFT 技术。

P3784 [SDOI2017]遗忘的集合

上上题的扩展练习。

P4705 玩游戏

应用练习。以及关于一个经典问题的 trick。

P5401 [CTS2019]珍珠

应用练习。

P4548 [CTSC2006]歌唱王国

虽然不是生成函数计数问题,但是概率生成函数相关的知识也应该了解一下。不需要多项式技术。

P3706 [SDOI2017]硬币游戏

概率生成函数的应用练习。

P5293 [HNOI2019]白兔之舞

应用练习。前置知识:单位根反演,(和)Bluestein 算法(类似的思想)。

P5206 [WC2019] 数树

应用练习。很有趣(迫真)的题目。涉及大量知识点。

P5326 [ZJOI2019]开关

好像有个从高斯消元出发的神秘做法但我不会……

后记

吾生也有涯,数数之毒瘤也无涯,我只能帮各位到这了……


  1. P4841 - [集训队作业2013] 城市规划
  2. CF438E - The Child and Binary Tree
  3. P4451 - [国家集训队] 整数的lqp拆分
  4. P4491 - [HAOI2018] 染色
  5. P4389 - 付公主的背包
  6. P5900 - 无标号无根树计数
  7. P3784 - [SDOI2017] 遗忘的集合
  8. P4705 - 玩游戏
  9. P5401 - [CTS2019] 珍珠
  10. P4548 - [CTSC2006] 歌唱王国
  11. P3706 - [SDOI2017] 硬币游戏
  12. P5293 - [HNOI2019] 白兔之舞
  13. P5206 - [WC2019] 数树
  14. P5326 - [ZJOI2019] 开关