本文目前是笔记的形式,可能观点比较散。

初衷是把生成函数的部分复习一下。

首先要理解一件事:生成函数是理解问题的方式,而多项式则是计算的方法。因此你经常看到“生成函数与多项式”之类的博客标题,但不能把生成函数和多项式混为一谈。

事实上,在把问题转化为生成函数后,剩下的式子转化与代码实现都属于多项式的范畴。但这两步都是不可缺的。

强烈建议在做生成函数题的时候,推完式子时,先手算一下样例看对不对,对了再写代码。

另外,本文的所有例题均带有 生成函数 多项式 EGF 标签。

EGF 与 OGF

OGF 的定义:,表示序列的生成函数。

EGF 的定义:,表示序列的指数生成函数。

再次强调,生成函数只是理解问题的方式。因此你可能发现,EGF 的实现和 OGF 的实现是差不多的——只不过多乘一个阶乘而已。你甚至可以认为,EGF 是的 OGF。这是理解方式的转变。然而实际上,生成函数也就只是一种理解问题的技巧

OGF 和 EGF 的加法,都是对应项系数相加。

OGF 的乘法:。表达的是卷积的运算。

EGF 的乘法:。表达的是带组合系数的卷积运算。

OGF 的多个函数的乘法,表达的是类似多个背包合并的运算。而 EGF 的多个函数的乘法,表达的是类似多个序列合并(同一个序列里的相对顺序不计贡献)的运算(多重组合数)。两者的区别是,背包中的物品是不考虑顺序的,而序列则是要考虑顺序的。

因此在理解问题的时候,可以先转化为序列问题或者背包问题,再用生成函数来理解。

PKUWC2018 猎人杀

猎人。每个猎人只有一个固定的技能:死亡后必须开一枪,且被射中的人也会死亡。

假设当前活着的人有,那么有的概率向猎人开枪。

第一枪由你打,目标选择方法和猎人一样。由于开枪导致的连锁反应,所有猎人最终都会死亡。求号猎人最后一个死的概率。

分治 NTT

生成函数部分

按照原题意,每杀一个人,概率空间会发生变化。这样就没法做了。

如果我们允许向死人开枪呢?

向死人开枪,相当于浪费一回合。但这无关紧要。因为我们要求的答案和回合数无关。我们只关心一号猎人最后一个死的概率。

这样的话概率空间就一样了。那么我们的问题就可以转化为一个序列问题:

每次有的概率在序列的末位加入。求:

  • 最后一个数是,且只出现了这一次,
  • 都在序列中出现过

的序列出现的概率。

(这个序列的长度是不固定的,可能无限长)

如果我们按照一个一个在序列末尾加数的方式理解问题,那么要求都在序列中出现过就比较难处理。因此我们考虑另一个理解方式——个序列的合并。

假设你有个序列,第个序列是)。特殊地,。你要把他们合并成一个序列,使得出现在最后一个位置,求方案数?

容易发现这个问题和上面的问题是等价的。我们知道概率乘方案数等于这些方案的概率。因此我们求出每个序列的出现概率——即,选出的概率,那么乘起来再乘上方案数,就是这些方案的概率。而方案数就是一个简单的多重组合数。

这是从序列合并的角度理解,那么接下来我们将其转化为生成函数的理解。

对于,由于我们可以选择任意个数的,因此他们的生成函数应该是无穷级数的 EGF。不妨设

含义是,选择的概率是,由于我们至少选一个,因此

对于,我们只要求出现一次且在末尾,因此它不会影响方案数,只需要乘一次的概率即可。因此我们可以不用求它的生成函数。也可以理解为,的生成函数是一个常数

那么序列的生成函数(EGF)就是

其中表示长度为的序列出现的概率。那么我们要求的就是EGF 系数的和。

注意,对于 EGF,我们说的EGF 系数是指,即,系数才是指

多项式部分

接下来就是多项式转化的部分了。

首先,因此

首先我们知道,的 EGF 系数和就是等比数列求和,可以化为封闭形式。可惜的乘积的 EGF 系数和并不是,因此我们只能想办法求出对与每个的系数值(出现次数)。因此接下来的问题就是一个类似背包的计算。然而这不能直接容斥。注意到,因此不妨设表示出现的次数(带容斥系数),容易发现的 OGF 是

那么直接使用分治 + 多项式乘法计算即可。

可以先把当作来算,最后再全部除以即可。

时间复杂度

代码

UNR3 百鸽笼

个数。设

接下来进行次操作:每次在的数中等概率随机选择一个数,然后把减 1。

最后一定会剩下一个。现在问对于,在操作后的概率。

插板法 无穷级数转封闭形式

生成函数部分

不妨考虑的概率。

不妨加一次操作。因为选择最后一个空的笼子的概率是

仍然考虑使用生成函数的方式理解。首先,根据类似的思路,我们可以把操作变成,每次在所有数中等概率选择。这样的话序列的长度就可能是无限长的,它需要满足的条件是:

  • 对于的出现次数
  • 在序列中出现了恰好次,且最后一个数是

这里可能会有一个小疑问:为什么是出现次而不是次?其实如果是出现次的话,那么就没有最后一个数是的限制。我们相当于删掉了第列里的一个格子,那么这和原问题就是不等价的。

仍然是考虑每个数的生成函数。对于

特殊地,对于,我们考虑除了最后一个之外的

那么整个序列的生成函数就是

我们要求的仍是系数和。

多项式部分

首先,对于

为了方便表示,设,那么就可以得到。因此整个序列的生成函数可以化为

如果我们把除了之外的部分展开,那么可以得到形如的一个多项式(二维数组)。要计算它的 EGF 系数和,我们可以对每一项分别计算 EGF 系数和再相加。那么对这个单项式展开会得到

它的 EGF 系数和就是

这里要补充一个知识。我们知道等比数列的封闭形式是。那么考虑。它的展开形式是,第项的系数实际上是把分成个非负变量的方案数,也就是插板法。因此

应用这个补充的知识,我们可以得到上式的封闭形式为。注意,UOJ 的官方题解中得到的系数是带了一个的,因为它算的是 OGF 系数,不是 EGF 系数。还是那句话,两者只是理解方式的不同,代码实现是相似的。

得出封闭形式那么就容易计算了。

最后,考虑到我们要计算每个的概率,那么我们可以先把所有的乘起来。然后每次除掉对应的 EGF,再求答案即可。

时间复杂度同阶)。

事实上,生成函数做法和容斥的做法,代码几乎一样。

代码

附 UNR#3 的题解链接:

UNR #3 day1

UNR #3 day2

UR19 通用测评号

个变量,初值为。给出两个数)。每次会在的变量中等概率随机选一个加,直到所有变量都。问操作完后的变量的个数的期望。

递推 微分方程

生成函数部分

个变量之间是等价的。因此我们可以计算操作完之后的概率,然后乘就是答案。

仍然考虑把的条件去掉。每次在所有变量中选一个加,直到所有变量。那么我们要求的就是的概率,不过我们还要求中至少出现一个(因为你最后一次操作一定是把某个变量从变成),而如果有多个的话,你最后一次操作在什么位置,也要计入方案中。这就比较难计数。

不妨考虑另一种理解方式。仍然要把的条件去掉。但我们可以理解为:让的这次操作会产生的贡献。其他时候都没有贡献。问贡献的期望。

在什么时候会产生贡献?首先你要选出,且当前选的这一次(操作序列的最后一个变量)是。其次中至少有一个变量。这样理解的好处是,我们不用考虑最后一次操作的方案数(因为操作仍没有结束),只用考虑生成这类序列的方案数。那么就可以使用生成函数了。

那么的 EGF 是。对于)的 EGF,我们可以把至少一个变量容斥为 1 减去所有变量的概率。那么的概率的 EGF 是。因此我们得到了整个序列的生成函数:

多项式部分

考虑转化:

我们要计算的仍是的 EGF 系数和。仍然考虑求出类似的形式。

为了方便表示,设。我们先求出关于的生成函数,就可以快速转化为关于的生成函数。

那么换元之后,我们得到

不妨设,然后把后面的式子二项式展开:

到这里我们已经可以直接计算了。我们可以计算。然后把他们加起来就能得到了。但我们仍然可以继续优化。

首先,可以发现。因此

不妨设。那么上式就可以表示为

转 OGF 系数就是,即

这样就可以递推求了,时间复杂度

代码

EGF 转 OGF

考虑,我们要将其转为

对于长度有限的生成函数,我们可以直接乘阶乘。

对于一些无穷级数,则需要做代数变换。例如。它的展开形式为。我们要将它转为,因此我们说EGF 转 OGF

接下来的部分题目会用到这一技巧。

还是那句话。这只是一种理解方式的转变。上文的 EGF 系数和,也可以使用 EGF 转 OGF 理解为,转为后求

ZJOI2019 开关

你有个开关,初始时全为 0。每次你会以的概率按动第个开关。给出一个状态(01 串),问期望按多少次才能第一次按到这个状态。

EGF 转 OGF 导数 概率生成函数 期望

生成函数部分

为了避免歧义,我们用来表示题目中的。相信在做过之前的若干题目后,大家对 EGF 都有了一定的理解。因此接下来的描述就不会像之前那么详细了。

我们要求的是第一次按出的期望次数,这里有一个经典的套路。我们求出按次后第一次到达的概率,记为。那么它的 OGF 就是。则期望就是

那么如何求出?“第一次到达”这个条件比较烦。考虑构造生成函数方程:到达的概率 = 第一次到达后,经过若干次操作(可能是 0 次)又到达的概率。

到达的概率可以用 EGF 表示。要到达,则某些开关要按奇数次,有些要按偶数次。那么这两种的 EGF 分别是。因此容易得到

第一次到达后又到达,相当于我先到达。然后经过若干次操作后回到。因此我们再考虑求出一个 EGF 表示,回到原状态的概率(即,所有开关都按偶数次):

那么我们 EGF 转 OGF,设的 OGF 分别为。那么我们可以得到。即

多项式部分

根据简单的函数求导法则可以得知。那么。于是我们想办法计算的系数和即可。

我们仍从 EGF 入手。以为例。

首先,可以表示为的形式(注意,这里是没有的),其中。那么使用 EGF 转 OGF 就可以得到

那么它的系数和就是。不过有一个小问题,如果,那么做分母的项当时就没有意义了。

这也好办。我们有两种思路:

  1. 的分子分母同乘
  2. 的分子分母同乘(把都乘一个)。

第二种思路不大可行。因为

只乘一个不足以解决问题。因此我们考虑第一种思路。

。那么首先,且。然后使用简单的求导法则得到

那么

同理。

综上所述,我们只需要求出形式即可,这个可以背包计算。同理。时间复杂度。当然可以分治 +NTT 优化。

事实上,在实现的时候,连最开头的那个部分都可以不用除了(分子分母同乘)。

代码

喂鸽子

个变量,初值为。每次等概率随机选择一个变量加 1,直到所有变量都。问期望的操作次数。

EGF 转 OGF

由于这题和通用评测号相似,因此也不会详细讲述。

生成函数部分

不妨钦定是最后一个变成的,最后把答案乘即可。那么可以得到关于操作次数(减 1)的概率的 EGF:

EGF 转 OGF 后的生成函数。

那么关于操作次数的概率的 OGF 是。因此我们要求的就是

多项式部分

众所周知。因此

接下来考虑变换 EGF。首先

不妨设,那么

可以利用相同的方式递推求出。然后我们可以把表示为的形式()。我们要求,那么我们把每一项分别 EGF 转 OGF,然后相加即可。

展开得到

EGF 转 OGF 得到,转化为封闭形式是

因此。则通过简单的导数法则再加一些代数变换得知

由于,所以不会出现分母为的情况。直接计算即可。

代码