「学习笔记」生成函数入门
source link: https://blunt-axe.github.io/2019/12/12/20191212-Generating-Function-Notes/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在数学中，某个序列 的母函数（又称生成函数，英语：Generating Function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
摘自维基百科。生成函数分为多种，本文将主要介绍普通生成函数（Ordinary Generating Function）和指数生成函数（Exponential Generating Function）。另外，本文还会提到大部分的多项式算法，用来解决生成函数的题目。
入门文章推荐：
广义二项式定理
广义二项式定理是卡特兰数通项的前置技能。我们对广义的组合数有如下定义：
那么下式始终成立：
当 为整数的时候上式就是传统的二项式定理。
复合函数求导
对一个复合函数 求导：
这样的求导法则被称为 “链式法则”。
普通生成函数
普通生成函数，英文 Ordinary Generating Function，简称 OGF。对于序列 ，它的普通生成函数 。另外如果 是某个离散随机变量的概率质量函数，它的生成函数被称为概率生成函数。
BZOJ 3028 食物
题目大意：
由若干种食物，每种食物有一个限制（比如只能选不超过 个，只能选奇数个等，具体看题），问选出 份食物的方案数。
数据范围：。
思路分析：
考虑把所有食物的生成函数乘起来：
于是我们考虑用二项式定理展开：
于是就有 ，直接计算即可。
BZOJ 3027 Sweet
题目大意：
有 罐糖，第 罐有 个，问选出 个糖的方案数。
数据范围：。
思路分析：
我们要求的是生成函数：
中 的系数的和。
发现 很小，所以可以 枚举 的每一项，之后就只需要计算一个组合数的前缀和：
直接计算即可，时间复杂度 。
推导卡特兰数通项
卡特兰数的第 项表示 个结点的二叉树数量（不带标号，区分左右子树）。记卡特兰数的第 项为 ，那么 ，且对于 有递推式：
记 表示卡特兰数的生成函数，那么我们有：
最后 是因为要考虑 的边界。那么我们考虑解方程：
在第四行舍掉减号是因为如果取减号那么 时没有意义。
那么我们首先要计算 ，用二项式定理展开：
考虑计算 ：
注意上式只在 时是正确的， 时 。经过上述的推导，我们有：
代回原式得到：
所以我们就得到了卡特兰数的通项公式：
BZOJ 4001 概率论
题目大意：
问 个点的二叉树期望有几个叶子。
数据范围：。
思路分析：
设 表示 个结点的二叉树的叶子总数，那么我们有 ，对于 有递推式：
其中 表示卡特兰数的第 项，也就是 。那么我们记卡特兰数的 OGF 为 ， 的 OGF 为 ，那么我们有：
在上一题中我们知道 ，那么我们就有：
于是我们就得到了 ，那么答案就是：
直接计算即可。当然也有更巧妙的方法，观察到：
那么我们就得到了：。
Codeforces 438E 小朋友与二叉树
「Codeforces 438E」The Child and Binary Tree
题目大意：
给定 个数 ，问有多少棵点上有数的二叉树，满足点上的数是某个 ，并且点权和为 。对于所有 求出答案。
数据范围：。
思路分析：
设 的 OGF 为 ，答案的 OGF 为 ，那么根据题意，有：
考虑解方程：
这里要舍掉减号。于是使用多项式求逆、开根即可计算，时间复杂度 。
指数生成函数
指数生成函数，英文是 Exponential Generating Function，简称 EGF。对于序列 ，它的指数生成函数为：
指数生成函数一般被用来求解有标号的计数问题，它可以简化运算，因为有以下泰勒级数成立：
POJ 3734 Blocks
题目大意：
有 个带标号的格子，每个格子染 种颜色之一，要求最后第 种颜色是偶数，问方案数。
数据范围：。
思路分析：
格子是有标号的，考虑答案的指数生成函数：
因为 ，所以有：
所以答案 就等于 ，直接计算即可。
BZOJ 3456 城市规划
题目大意：
问有多少个带标号的 个点的联通图。
数据范围：。
思路分析：
记 个点的带标号无向图的个数为 ，那么 的指数生成函数为：
记 个点的带标号联通图的个数为 ，那么 的指数生成函数为：
发现 ，所以我们把 做多项式对数函数就行了。时间复杂度 。
51nod 1728 不动点
题目大意：
求有多少个映射 ，使得 。
数据范围：。时限 。
思路分析：
其实就是求 个点的每个树的深度都不超过 的有根森林的个数。记 时的指数生成函数为 ，那么显然有 。考虑如何从 推到 。对于一个 个点的有根树我们枚举一个根，去掉这个根后其他的点就会形成大小为 的有根森林。如果令 个点的深度不超过 的有根树个数的指数生成函数为 ，那么就有 ，推一下发现 。而我们又有 ，所以就有 。时间复杂度 ，注意常数优化。
Codeforces 891E Lust
题目大意：
给定 个数 ，作 次操作，每次随机选一个数 ，把 ，问最后 的期望。
数据范围：。
思路分析：
发现答案等于一开始所有数的乘积减去操作完后所有数的乘积，所以只要算操作完后所有数的乘积的期望。考虑算出每个数的 EGF 最后乘起来。 的 EGF 是：
所以答案的 EGF 是：
我们要求的期望 满足 。我们 算出 后考虑计算答案：
直接计算，总复杂度 。
Recommend
-
25
本文是哥伦比亚大学研究生张威在生成模型上的学习笔记，由毕业于新西兰奥克兰理工大学的燕子石翻译。机器之心之前曾介绍过张威所写的
-
43
参考 golang 函数以及函数和方法的区别 在接触到go之前，我认为函数和方法只是同一个东西的两个名字而已（在我熟悉的c/c++，python，java中没有明...
-
8
Positional Argument 最普通常见的参数，函数调用时必须按照定义顺序准确传递，而且数量也必须一样，不能多也不能少。位置参数还有一种传参方式：通过关键字。如果在函数调用时给出参数名，这样就不必按照定义顺序传参了，因为解释器可以自己根据参数...
-
20
0x00 前言 shellcode是一段机器码，常用作漏洞利用中的载荷(也就是payload) 在渗透测试中，最简单高效的方式是通过metasploit生成shellcode，然而在某些环境下，需要定制开发自己的shellcode，所以需要对shellcode的开发作进一步研究
-
16
[PyTorch 学习笔记] 5.2 Hook 函数与 CAM 算法哈尔滨工程大学 计算机硕士在读 本章代码：这篇文章主要介绍了如何使用 Hook 函数提取网络中的特征...
-
8
我是歌谣 我有个兄弟 巅峰的时候排名c站总榜19 叫前端小歌谣 曾经我花了三年的时间创作了他 现在我要用五年的时间超越他 今天又是接近兄弟的一天人生难免坎坷 大不了从头再来 歌谣的意志是永恒的 放弃很容易 但是坚持一定很酷
-
5
1. 数论函数 本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。 1.1 相关定义 数论函数：定义域为正整数的函数称为 数论函数。因其...
-
4
函数在 Go 语言中属于“一等公民”，拥有“一等公民”待遇的语法元素可以存储在变量中，可以作为参数传递给函数，可以在函数内部创建并可以作为返回值从函数返回。 1，函数的定义 Go 函数样式：
-
3
复杂数据类型 特点：多个数据变量地一个集合体，可以自己命名 种类：枚举、数组和结构体 枚举：整型常量的集合 数组：任意变量类型的顺序存储的数据集合 结构...
-
6
Linux脚本学习笔记，log函数使用技巧 作者：微技术 2024-01-16 14:08:06 本文主要讲述的是一个关于记录shell脚本执行日志的日志脚本函数，在做shell脚本开发的过程中，常常要运行脚本来监测一些系统数据，但是我们...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK