生成函数回炉重造

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

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

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

事实上，在把问题转化为生成函数后，剩下的式子转化与代码实现都属于多项式的范畴。

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

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

EGF 与 OGF

OGF 的定义：$F(x)=\sum a_ix^i$，表示序列$a_i$的生成函数。

EGF 的定义：$\hat{F}(x)=\sum a_i\frac{x^i}{i!}$，表示序列$a_i$的指数生成函数。

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

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

OGF 的乘法：$a_ix^i\times b_jx^j=a_ib_jx^{i+j}$。表达的是卷积的运算。

EGF 的乘法：$a_i\frac{x_i}{i!}\times b_j\frac{x^j}{j!}=a_ib_j\binom{i+j}{i}\frac{x^{i+j}}{(i+j)!}$。表达的是带组合系数的卷积运算。

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

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

PKUWC2018 猎人杀

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

假设当前活着的人有$[i_1,\cdots,i_m]$，那么有$\frac{w_{i_k}}{\sum_{j=1}^m w_{i_j}}$的概率向猎人$i_k$开枪。

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

$w_i>0,1\le \sum w_i\le 10^5$。

分治 NTT

生成函数部分

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

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

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

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

每次有$p_i=\frac{w_i}{\sum_{j=1}^n w_j}$的概率在序列的末位加入$i$。求：

• 最后一个数是$1$，且$1$只出现了这一次，
• $2,\cdots,n$都在序列中出现过

的序列出现的概率。

（这个序列的长度是不固定的，可能无限长）

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

假设你有$n$个序列，第$i$个序列是$c_i$个$i$（$c_i>0$）。特殊地，$c_1=1$。你要把他们合并成一个序列，使得$1$出现在最后一个位置，求方案数？

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

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

对于$2\le j\le n$，由于我们可以选择任意个数的$i$，因此他们的生成函数应该是无穷级数的 EGF。不妨设

$$\hat{f_j}(x)=\sum_{i\ge 1}\frac{(p_jx)^i}{i!}$$

含义是，选择$i$个$j$的概率是$p_j^i$，由于我们至少选一个，因此$i\ge 1$。

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

那么序列的生成函数（EGF）就是

$$\hat{F}(x)=p_1\prod_{j=2}^n\hat{f_j}(x)$$

其中$[x^i]\hat{F}(x)$表示长度为$i$的序列出现的概率。那么我们要求的就是$\hat{F}(x)$的EGF 系数的和。

注意，对于 EGF$\hat{F}(x)=\sum a_i\frac{x^i}{i!}=\sum b_ix^i$，我们说的EGF 系数是指$a_i$，即$b_i\cdot i!$，系数才是指$b_i$。

多项式部分

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

首先$\hat{f_j}=e^{p_jx}-1$，因此

$$\hat{F}(x)=p_1 \prod_{j=2}^n(e^{p_jx}-1)$$

首先我们知道，$e^{px}$的 EGF 系数和就是等比数列求和，可以化为封闭形式$\frac{1}{1-p}$。可惜$e^{px}$与$e^{qx}$的乘积的 EGF 系数和并不是$\frac{1}{1-p}\cdot \frac{1}{1-q}$，因此我们只能想办法求出对与每个$t$，$e^{tx}$的系数值（出现次数）。因此接下来的问题就是一个类似背包的计算。然而这不能直接容斥$\frac{1}{1-\sum p}$。注意到$\sum p_i\le 10^5$，因此不妨设$g_i$表示$\frac{1}{1-i}$出现的次数（带容斥系数），容易发现$g_i$的 OGF 是

$$\prod_{j=2}^n(x^{p_j}-1)$$

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

可以先把$p_j$当作$w_j$来算，最后再全部除以$\prod w_i$即可。

时间复杂度$O(n\log_2^2n)$。

代码

UNR3 百鸽笼

有$n$个数$a_i$。设$\sum_{i=1}^na_i=m$。

接下来进行$m-1$次操作：每次在$>0$的数中等概率随机选择一个数$a_x$，然后把$a_x$减 1。

最后一定会剩下一个$1$。现在问对于$1\le i\le n$，在操作后$a_i=1$的概率。

$1\le a_i\le 30,n\le 30$。

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

生成函数部分

不妨考虑$i=1$时$a_i=1$的概率。

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

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

• 对于$2\le i\le n$，$i$的出现次数$\ge a_i$。
• $1$在序列中出现了恰好$a_1$次，且最后一个数是$1$。

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

仍然是考虑每个数的生成函数。对于$2\le j\le n$：

$$\hat{f_j}(x)=\sum_{i\ge a_j}\frac{(\frac{1}{n}x)^i}{i!}$$

特殊地，对于$i=1$，我们考虑除了最后一个$1$之外的$1$：

$$\hat{f_1}(x)= \frac{(\frac{1}{n}x)^{a_1-1}}{(a_1-1)!}$$

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

$$\hat{F}(x)=\frac{1}{n}\prod_{i=1}^n\hat{f_i}(x)$$

我们要求的仍是系数和。

多项式部分

首先，对于$2\le j\le n$：

$$\hat{f_j}(x)=\sum_{i\ge a_j}\frac{(\frac{1}{n}x)^i}{i!}=e^{\frac{1}{n}x}-\sum_{i=0}^{a_j-1}\frac{(\frac{1}{n}x)^i}{i!}$$

为了方便表示，设$\hat{S}(j)=\sum_{i=0}^j\frac{(\frac{1}{n}x)^i}{i!}$，那么就可以得到$\hat{f_j}(x)=e^{\frac{1}{n}x}-\hat{S}(a_j-1)$。因此整个序列的生成函数可以化为

$$\hat{F}(x)=\frac{1}{n} \frac{(\frac{1}{n}x)^{a_1-1}}{(a_1-1)!} \prod_{j=2}^n(e^{\frac{1}{n}x}-\hat{S}(a_j-1))$$

如果我们把除了$e$之外的部分展开，那么可以得到形如$\sum_{m,t} e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$的一个多项式（二维数组）。要计算它的 EGF 系数和，我们可以对每一项$e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$分别计算 EGF 系数和再相加。那么对这个单项式展开$e$会得到

$$c_{m,t}\sum_{i\ge 0}\left(\frac{m}{n}\right)^i\binom{i+t}{i}\frac{x^{i+t}}{(i+t)!}$$

它的 EGF 系数和就是

$$c_{m,t}\sum_{i\ge 0}\left(\frac{m}{n}\right)^i\binom{i+t}{i}$$

这里要补充一个知识。我们知道等比数列的封闭形式是$\sum_{i\ge0} x^i=\frac{1}{1-x}$。那么考虑$\frac{1}{(1-x)^t}$。它的展开形式是$(\sum_{i\ge 0}x^i)^t$，第$[x^i]$项的系数实际上是把$i$分成$t$个非负变量的方案数，也就是插板法$\binom{i+t-1}{i}$。因此$\frac{1}{(1-x)^t}=\sum_{i\ge 0}x^i\binom{i+t-1}{i}$。

应用这个补充的知识，我们可以得到上式的封闭形式为$c_{m,t}\frac{1}{(1-\frac{m}{n})^{t+1}}=c_{m,t}\left(\frac{n}{n-m}\right)^{t+1}$。注意，UOJ 的官方题解中得到的系数是带了一个$t!$的，因为它算的是 OGF 系数，不是 EGF 系数。还是那句话，两者只是理解方式的不同，代码实现是相似的。

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

最后，考虑到我们要计算每个$i$的概率，那么我们可以先把所有的$(e^{\frac{1}{n}x}-\hat{S}(a_j-1))$乘起来。然后每次除掉$i$对应的 EGF，再求答案即可。

时间复杂度$O(n^6)$（$a_i$和$n$同阶）。

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

代码

附 UNR#3 的题解链接：

UNR #3 day1

UNR #3 day2

UR19 通用测评号

有$n$个变量$x_i$，初值为$0$。给出两个数$a,b$（$a>b$）。每次会在$<a$的变量中等概率随机选一个加$1$，直到所有变量都$\ge b$。问操作完后$=a$的变量的个数的期望。

$1\le n\le 250,1\le b<a\le 250$。

递推 微分方程

生成函数部分

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

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

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

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

那么$x_1$的 EGF 是$\frac{1}{n}\frac{(\frac{1}{n}x)^{a-1}}{(a-1)!}$。对于$x_j$（$2\le j\le n$）的 EGF，我们可以把至少一个变量$<b$容斥为 1 减去所有变量$\ge b$的概率。那么$x_j\ge b$的概率的 EGF 是$\hat{f}(x)=\sum_{i\ge b}\frac{(\frac{1}{n}x)^i}{i!}$。因此我们得到了整个序列的生成函数：

$$\hat{F}(x)=\frac{1}{n}\frac{(\frac{1}{n}x)^{a-1}}{(a-1)!}\left( \left(e^{\frac{1}{n}x}\right)^{n-1}-\hat{f}(x)^{n-1}\right)$$

多项式部分

考虑转化：

$$\hat{F}(x)=\frac{1}{n}\frac{(\frac{1}{n}x)^{a-1}}{(a-1)!}\left( e^{\frac{n-1}{n}x}- \left(e^{\frac{1}{n}x}-\sum_{i=0}^{b-1}\frac{(\frac{1}{n}x)^i}{i!}\right)^{n-1} \right)$$

我们要计算的仍是$\hat{F}(x)$的 EGF 系数和。仍然考虑求出类似$\sum e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$的形式。

为了方便表示，设$v=\frac{1}{n}x,u=e^{v}$。我们先求出关于$v$的生成函数，就可以快速转化为关于$x$的生成函数。

那么换元之后，我们得到

$$\hat{F}(v)=\frac{1}{n}\frac{v^{a-1}}{(a-1)!}\left( u^{n-1}-\left(u-\sum_{i=0}^{b-1}\frac{v^i}{i!}\right)^{n-1}\right)$$

不妨设$\hat{S}=\sum_{i=0}^{b-1}\frac{v^i}{i!}$，然后把后面的式子二项式展开：

$$\begin{aligned} \hat{F}(v) &=\frac{1}{n}\frac{v^{a-1}}{(a-1)!}\left(u^{n-1}- \sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j\hat{S}^ju^{n-1-j} \right)\\ &=-\frac{1}{n}\frac{v^{a-1}}{(a-1)!} \sum_{j=1}^{n-1}\binom{n-1}{j}(-1)^j\hat{S}^ju^{n-1-j} \end{aligned}$$

到这里我们已经可以直接计算了。我们可以$O(n^2b\log_2(nb))$计算$\hat{S}^1,\cdots,\hat{S}^{n-1}$。然后把他们加起来就能得到$c_{m,t}$了。但我们仍然可以继续优化。

首先，可以发现$\hat{S}'=\hat{S}-\frac{v^{b-1}}{(b-1)!}$。因此

$$\begin{aligned} (\hat{S}^j)' &=j\hat{S}'\hat{S}^{j-1} \\ &=j\left( \hat{S}-\frac{v^{b-1}}{(b-1)!}\right)\hat{S}^{j-1} \\ &=j\left(\hat{S}^j-\frac{v^{b-1}}{(b-1)!}\hat{S}^{j-1}\right) \\ \end{aligned}$$

不妨设$\hat{S}^j=\sum p_i\frac{v^i}{i!}$，$\frac{v^{b-1}}{(b-1)!}\hat{S}^{j-1}=\sum q_i\frac{v^i}{i!}$。那么上式就可以表示为

$$p_{i+1}\frac{v^{i}}{i!}=j\left(p_i\frac{v^i}{i!}-q_{i}\frac{v^i}{i!}\right)$$

即$p_{i+1}=j(p_i-q_i)$。

转 OGF 系数就是$p'_{i+1}(i+1)!=j(p'_ii!-q'_ii!)$，即$p'_{i+1}=\frac{j(p'_i-q'_i)}{i+1}$。

这样就可以递推求$\hat{S}^j$了，时间复杂度$O(n^2b)$。

代码

EGF 转 OGF

考虑$\hat{F}(x)=\sum_{i\ge 0}a_i\frac{x^i}{i!}$，我们要将其转为$F(x)=\sum_{i\ge 0}a_i$。

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

对于一些无穷级数，则需要做代数变换。例如$\hat{F}(x)=e^{ax}$。它的展开形式为$\hat{F}(x)=\sum_{i\ge 0}\frac{(ax)^i}{i!}$。我们要将它转为$F(x)=\sum_{i\ge 0}(ax)^i=\frac{1}{1-ax}$，因此我们说$e^{ax}$的EGF 转 OGF为$\frac{1}{1-ax}$。

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

还是那句话。这只是一种理解方式的转变。上文的 EGF 系数和，也可以使用 EGF 转 OGF 理解为，$\hat{F}$转为$F$后求$F(1)$。

ZJOI2019 开关

你有$n$个开关，初始时全为 0。每次你会以$\frac{p_i}{\sum_{j=1}^n p_j}$的概率按动第$i$个开关。给出一个状态$s$（01 串），问期望按多少次才能第一次按到这个状态。

$n\le 100,\sum p_i\le 5\times 10^4$。

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

生成函数部分

为了避免歧义，我们用$a_i$来表示题目中的$\frac{p_i}{\sum_{j=1}^n p_j}$。相信在做过之前的若干题目后，大家对 EGF 都有了一定的理解。因此接下来的描述就不会像之前那么详细了。

我们要求的是第一次按出$s$的期望次数，这里有一个经典的套路。我们求出按$i$次后第一次到达$s$的概率，记为$h_i$。那么它的 OGF 就是$H(x)=\sum_{i\ge 0}h_i x^i$。则期望就是$\sum_{i\ge 0}h_i\cdot i=H'(1)$。

那么如何求出$H$？“第一次到达$s$”这个条件比较烦。考虑构造生成函数方程：到达$s$的概率 = 第一次到达$s$后，经过若干次操作（可能是 0 次）又到达$s$的概率。

到达$s$的概率可以用 EGF 表示。要到达$s$，则某些开关要按奇数次，有些要按偶数次。那么这两种的 EGF 分别是$\frac{e^x-e^{-x}}{2}$和$\frac{e^x+e^{-x}}{2}$。因此容易得到

$$\hat{F}(x)=\prod_{i=1}^n \frac{e^{a_ix}+(-1)^{s_i}e^{-a_ix}}{2}$$

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

$$\hat{G}(x)=\prod_{i=1}^n\frac{e^{a_ix}+e^{-a_ix}}{2}$$

那么我们 EGF 转 OGF，设$\hat{F}$和$\hat{G}$的 OGF 分别为$F,G$。那么我们可以得到$HG=F$。即$H=\frac{F}{G}$。

多项式部分

根据简单的函数求导法则可以得知$H'=\frac{F'G-FG'}{G^2}$。那么$H'(1)=\frac{F'(1)G(1)-F(1)G'(1)}{G^2(1)}$。于是我们想办法计算$F,F',G,G'$的系数和即可。

我们仍从 EGF 入手。以$F,F'$为例。

首先，$\hat{F}(x)$可以表示为$\sum_{j}f_je^{\frac{j}{m}x}$的形式（注意，这里是没有$\frac{x^i}{i!}$的），其中$m=\sum_{i=1}^n p_i$。那么使用 EGF 转 OGF 就可以得到

$$F(x)=\sum_j f_j \cdot \frac{m}{m-jx}$$

那么它的系数和就是$F(1)$。不过有一个小问题，如果$j=m$，那么$m -mx$做分母的项当$x=1$时就没有意义了。

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

1. 在$H=\frac{F}{G}$的分子分母同乘$(1-x)$；
2. 在$H'=\frac{F'G-FG'}{G^2}$的分子分母同乘$(1-x)^2$（把$F,F',G,G'$都乘一个$(1-x)$）。

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

$$F'(x) =\sum_j f_j \cdot \frac{m^2}{\left(m-jx\right)^2} \cdot \frac{j}{m}$$

只乘一个$(1-x)$不足以解决问题。因此我们考虑第一种思路。

设$\dot F(x)=F(x)(1-x)$，$\dot G(x)=G(x)(1-x)$。那么首先$\dot F(x)=F(x)=\sum_j f_j \cdot \frac{m(1-x)}{m-jx}$，且$\dot F(1)=f_m$。然后使用简单的求导法则得到

$$\dot F'(x)=\sum_j f_j \frac{m(j-m)}{(m-jx)^2}$$

那么$\dot F'(1)=\sum_{j\ne m}f_j\frac{m}{j-m}$。

$\dot G$和$\dot G'$同理。

综上所述，我们只需要求出$\hat{F}$的$\sum_{j}f_je^{\frac{j}{m}x}$形式即可，这个可以$O(nm)$背包计算。$\hat{G}$同理。时间复杂度$O(nm)$。当然可以分治 +NTT 优化。

事实上，在实现的时候，连最开头的$\frac{1}{2}$那个部分都可以不用除了（分子分母同乘$2^n$）。

代码

喂鸽子

有$n$个变量$x_i$，初值为$0$。每次等概率随机选择一个变量加 1，直到所有变量都$\ge k$。问期望的操作次数。

$n\le 50,k\le 1000$。

EGF 转 OGF

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

生成函数部分

不妨钦定$1$是最后一个变成$k$的，最后把答案乘$n$即可。那么可以得到关于操作次数（减 1）的概率的 EGF：

$$\hat{F}(x)=\frac{1}{n}\frac{(\frac{1}{n}x)^{k-1}}{(k-1)!}\prod_{j=2}^n\left(\sum_{i\ge k}\frac{(\frac{1}{n}x)^i}{i!} \right)$$

设$F$是$\hat{F}$EGF 转 OGF 后的生成函数。

那么关于操作次数的概率的 OGF 是$\dot F=F(x)\cdot x$。因此我们要求的就是$\dot F'(1)$。

多项式部分

众所周知$\dot F'(x)=F'(x)\cdot x+F(x)$。因此$\dot F'(1)=F'(1)+F(1)$。

接下来考虑变换 EGF。首先

$$\hat{F}(x)=\frac{1}{n}\frac{(\frac{1}{n}x)^{k-1}}{(k-1)!} \left(e^{\frac{1}{n}x}-\sum_{i=0}^{k-1}\frac{(\frac{1}{n}x)^i}{i!} \right)^{n-1}$$

不妨设$\hat{S}=\sum_{i=0}^{k-1}\frac{(\frac{1}{n}x)^i}{i!}$，那么

$$\begin{aligned} \hat{F}(x) &=\frac{1}{n}\frac{(\frac{1}{n}x)^{k-1}}{(k-1)!} \left(e^{\frac{1}{n}x}-\hat{S} \right)^{n-1}\\ &=\frac{1}{n}\frac{(\frac{1}{n}x)^{k-1}}{(k-1)!} \sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j\hat{S}^je^{\frac{n-1-j}{n}x} \end{aligned}$$

可以利用相同的方式$O(n^2k)$递推求出$\hat{S}^j$。然后我们可以把$\hat{F}(x)$表示为$\sum e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$的形式（$0\le m<n$）。我们要求$F(x)$，那么我们把每一项$e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$分别 EGF 转 OGF，然后相加即可。

把$e^{\frac{m}{n}x}c_{m,t}\frac{x^t}{t!}$展开得到$c_{m,t}\sum_{i\ge 0}\binom{i+t}{i}(\frac{m}{n})^i\frac{x^{i+t}}{(i+t)!}$。

EGF 转 OGF 得到$c_{m,t}\sum_{i\ge 0}\binom{i+t}{i}(\frac{m}{n})^ix^{i+t}$，转化为封闭形式是$c_{m,t}x^t(\frac{n}{n-mx})^{t+1}$。

因此$F(x)=\sum c_{m,t}x^t(\frac{n}{n-mx})^{t+1}$。则通过简单的导数法则再加一些代数变换得知

$$F'(x)=\sum c_{m,t}n^{t+1} \frac{ntx^{t-1}+mx^t}{(n-mx)^{t+2}}$$

由于$m<n$，所以不会出现分母为$0$的情况。直接计算$F'(1)$和$F(1)$即可。

代码