生成函数入门

比较严谨的东西就略过了,这里讲的主要是做题要用到的一些技巧。

这里个人认为生成函数的卷积本质上都是枚举了划分,有标号则需要组合数来分配标号(若这些物品本质一样,需要除掉阶乘),无标号不管。

OGF

$$
A(x) = \sum _{n \ge 0} a _n x ^n \\
h _n = \sum _{i = 0} ^n f _i g _{n - i} \Leftrightarrow H(x) = F(x) G(x)
$$

一些常用的表达式:

$$
[x ^m] \frac 1 {(1 - x) ^n} = {n + m - 1 \choose n - 1} \\
[x ^m] (1 + x) ^n = {n \choose m} \\
\ln (1 + x) = \sum _{n \ge 1} \frac {(-1)^{n+1}} n x ^n
$$

最后一个就是泰勒级数。

一些需要熟练的操作:

  1. 换元和移项。乘上 $x$ 或者求导积分是移项的两种方法,求导积分会额外带系数。
  2. 爆推式子然后转封闭形式。也就是要直接盯生成函数把封闭形式盯出来
  3. 求一些数列的通项。

付公主的背包

$n$ 个物品,每个物品有无限个,体积为 $v _i \in [1, m]$。

问总体积分别为 $1, \cdots, m$ 的方案数。

$n, m \le 10 ^5$

暴力就硬背包,$O(nm)$ 的。

实际上看到背包就要想到生成函数。玩了一下发现每个物品的生成函数是

$$
\sum _{n \ge 0} \left[ v _i | n \right] x ^n = \frac 1 {1 - x ^{v _i}}
$$

那么做背包相当于把生成函数全部卷积起来,令答案的生成函数为 $A(x)$:

$$
A(x) = \prod _{i = 1} ^n \frac 1 {1 - x^{v _i}}
$$

乘积不好处理,比较套路的想到先取 $\ln$ 再取 $\exp$:

$$
A(x) = \exp \left (\sum _{i = 1} ^n \ln \left (\frac 1 {1 - x ^{v _i}} \right) \right)
$$

回忆一下 $\ln \frac 1 {(1 + t)} = - \ln (1+t)$ 的泰勒展开式,将 $t = (-x) ^{v _i}$ 代入得到

$$
\ln \left (\frac 1 {1 - x ^{v _i}} \right) = \sum _{n \ge 1} [v _i | n] \frac {v _i} n x ^n
$$

注意这里是 $n \ge 1$,因为取 $\ln$ 后常数项变为 $0$。

推到这里的时侯发现已经可以算了:对于每个 $v _i$ 枚举其倍数去作贡献,可以 $O(n \log n)$ 地得到将 $\ln$ 求和的结果。

把这个式子 $\exp$ 回去即可,复杂度 $O(n \log n)$。

整数划分同理,只是物品是满的而已。

生成树

$n$ 个点的完全图,定义形如 $(i, i + 1)$ 的边为特殊边,以及一个有 $x$ 条特殊边的生成树的权值为 $\varphi (x)$。求所有生成树价值的和。

$n \le 10 ^6$

先填上特殊边再考虑方案数。

直接上 $\rm Prufer$ 序的一个定理:

  • $n$ 个点 $m$ 个连通块的无向图,将这些连通块连通起来的选边的方案数是 $n ^{m - 2} \prod _{i = 1} ^m s _i$,其中 $s _i$ 为第 $i$ 个连通块的大小

由于连通块数等于点数减边数,直接枚举连通块数算钦定了 $m$ 个连通块的方案数,最后二项式反演一下就可以了。

$n ^{m - 2}$ 暂且不管,主要是求后面的 $\prod$ 的部分。

考虑一个连通块的生成函数为

$$
F(x) = \sum _{n \ge 1} n x ^n = \frac x {(1 - x)^2}
$$

这里的连通块指的是连续的区间,所以应当为 OGF

$m$ 个连通块相当于是这个函数的 $m$ 次方,于是

$$
[x ^n] \left (F(x)\right) ^m = [x ^n] \frac {x ^m} {(1 - x)^{2m}} = {m + n - 1 \choose 2m - 1}
$$

没了。

猎人杀

$n$ 个猎人,每个猎人有仇恨值 $w _i$,每个猎人死后,会有 $\dfrac {w _i} {\sum _{\text{j is alive}} {w _j}}$ 的概率打掉猎人 $i$。求 $1$ 号猎人最后死亡的概率。

$\sum w _i \le 10 ^5$

下面可能会用 $w(S)$ 表示 $\sum _{i \in S} w_i$

首先要去除打了一个猎人后所带来的概率的后效性。

上面这个策略打到 $i$ 的概率等价于「不断开枪,可以打死的人,直至打中活的人」这个策略打到 $i$ 的概率。这是个很重要的转化。

于是开始转移。先设 $f(S)$ 表示钦定了 $S$ 集合内的人全部晚于 $1$ 号猎人死的概率。答案为 $\sum _{1 \not \in S} (-1) ^{|S|} f(S)$。

有转移方程($U$ 指全集):

$$
f(S) = \frac {w _1} {w(U)} + \frac {w(U) - w(S) - w _1} {w(U)} f(S)
$$

打中 $1$ 结束,打中 $S$ 非法,打中 $S$ 和 $1$ 之外的不变。

移下项得到
$$
f(S) = \frac {w _1} {w(S) + w _1}
$$

发现 $f(S)$ 的值只与 $w(S)$ 有关,并且 $w(U) \le 10 ^5$,于是将 $f$ 的定义域改造为整数,重化一下式子,看第 $i$ 个权值对答案产生了多少贡献:

$$
\sum _{i = 1} ^{w(U)} f(i) \sum _{1 \not \in S} (-1) ^{|S|} [w(S) = i]
$$

主要是求后面求和号的值。

发现暴力可以考虑背包,想起来实际上还有生成函数这么个东西。

那么每个猎人的生成函数应当是 $1 - x ^{w _i}$,故答案为:

$$
\sum _{i = 1} ^{w(U)} f(i) \left ([x ^i] \prod _{j = 2} ^n (1 - x ^{w _j}) \right)
$$

可以直接分治 NTT(注意不是 CDQ 的,就是普通分治)$O(n \log ^2 n)$;

也可以类似付公主的背包一样 $O(n \log n)$ 地得到求 $\ln$ 后的式子再 $\exp$ 回去。

当然建议用分治 NTT,考场上写个这个比写个整套板子快多了

实际上分治 NTT 的复杂度为 $O(w(U) \log ^2 w(U))$,而 $\exp$ 的复杂度为 $O(w \log w)$,优秀很多。付公主的背包分治就会复杂度不对。

  • 日常在多项式预处理时写了个 $n$ 而不是 $w(U)$……要注意这个东西。

EGF

$$
A(x) = \sum _{n \ge 0} a _n \frac {x ^n} {n!} \\
h _n = \sum _{i = 0} ^n {n \choose i} f _i g _{n - i} \Leftrightarrow H(x) = F(x) G(x)
$$

这是个奥妙重重的东西……一般用于有标号的计数中。

下面那个通常称为二项卷积。

注意这里积分和求导对应了移项,而乘 $x$ 对应了带系数的移项。

一些常用的表达形式:

$$
e ^x = \sum _{n \ge 0} \frac {x ^n} {n!} \\
\frac{e ^x + e ^{-x}} 2 = \sum _{n \ge 0} \frac {x ^{2n}} {(2n)!} \\
\frac{e ^x - e ^{-x}} 2 = \sum _{n \ge 0} \frac {x ^{2n + 1}} {(2n + 1)!}
$$

无向连通图个数

有几种做法。首先设 $f _n$ 表示 $n$ 个点的无向连通图的个数,$g _n$ 表示无向图的个数,可以知道 $g _n = 2 ^{n(n - 1) / 2}$。

那么考虑枚举 $1$ 号点所在的连通块的大小,有转移式:
$$
f _n = g _n - \sum _{i = 1} ^{n - 1} {n - 1 \choose i - 1} f _i g _{n - i}
$$
常规的分治 NTT 之类的就不提了,这里展示一下生成函数怎么做。

先把这个减号移到等式右边:
$$
g _n = \sum _{i = 1} ^{n} {n - 1 \choose i - 1} f _i g _{n - i}
$$
注意这个能够成立的前提是定义了 $g _0 = 1$。

然后改变一下 $i$ 的枚举:
$$
g _n = \sum _{i = 0} ^{n - 1} {n - 1 \choose i} f _{i + 1} g _{n - i - 1}
$$
发现这和二项卷积已经长得非常像了,但是 $f _{i + 1}$ 和这个 $n - 1$ 特别讨厌……

这时需要联想到求导相当于左移,而积分相当于右移。那么上面的式子等价于:
$$
G(x) = \int F’(x) G(x)
$$
把这个式子拆出来玩一下会发现和上面是符合的。

接下来就顺理成章:
$$
G(x) = \int F’(x) G(x) \\
G’(x) = F’(x) G(x) \\
F’(x) = \frac {G’(x)} {G(x)} \\
\int F’(x) = \int \frac {G’(x)} {G(x)} \\
F(x) = \ln (G(x))
$$
然后惊讶地发现求个 $\ln$ 就可以得到 $F(x)$ 了。

有些题也可以得到类似的式子,不过可能需要一些微分方程的基础知识才能解出来表达式;这个式子是最基础的。

上面算是比较严谨的推导,如果要真正考虑到其优美性质,会注意到:无向图由无向连通图组合而成

那么相当于是
$$
G(x) = \sum _{m \ge 0} \frac {F^m(x)} {m!}
$$
相当于是枚举这个图由 $m$ 个连通块构成。然后你会惊奇地发现后面就是 $\exp (F(x))$ 的展开式,于是同样的得到了 $F(x) = \ln (G(x))$。

硬证明的话,把 $F ^m(x)$ 拆出来看看:
$$
[x^n] F^m(x) = \sum _{S \text{ is a partition}} {n \choose s _1, s _2, \cdots, s _m} \prod _{i = 1} ^m f _{s _i}
$$
${n \choose s _1, s _2, \cdots, s _m}$ 是个多元组合数,等于 $\dfrac {n!} {s _1 ! s _2 ! \cdots s _m !}$。乘上这个东西相当于为每个连通图都分配了一个标号和位置。

但是无向图中,连通图的位置是没有关系的;所以最后要除掉一个 $m!$ 避免算重。

射命丸文的笔记

求 $n$ 个点的竞赛图的期望哈密顿回路数量。

$n \le 10 ^5$

首先哈密顿回路总数是好求的:对每条哈密顿回路分开考虑贡献, 发现是 $(n-1)! 2 ^{n(n - 1) / 2 - n}$。一条哈密顿回路肯定对应着一个环排列,环上的边固定方向后其他边可以任选方向。

于是问题变成了求强连通的竞赛图的数量。

需要知道一个结论:任意竞赛图缩点之后会得到一条链,链前面的节点向所有后面的节点均有连边,且方向固定。

所以一个竞赛图也可以看作强连通竞赛图的组合。但是由于是链,这时强连通竞赛图的位置是有意义的;所以
$$
\begin{aligned}
G(x) &= \sum _{m \ge 0} F^m(x) \\
&= \frac 1 {1 - F(x)}
\end{aligned}
$$
于是 $F(x) = 1 - \dfrac 1 {G(x)}$。多项式求逆即可。

用二项卷积的理论也是可以证明的。首先写出转移式:枚举拓扑序最小的强连通分量的大小,其他的点任意连边:
$$
f _n = g _n - \sum _{i = 1} ^{n - 1} {n \choose i} f _i g _{n - i}
$$
将 $g _0$ 定义成 $1$,而 $f _0$ 定义成 $0$,移个项:
$$
g _n = \sum _{i = 0} ^{n} {n \choose i} f _i g _{n - i}
$$
于是可以得到
$$
G(x) = F(x) G(x) + 1
$$
加一个 $1$ 是因为 $f _0 = 0, g _0 = 1$,所以 $F(x)G(x)$ 的常数项会少一个 $1$。(要着重注意这个小问题)

所以
$$
F(x) = 1 - \frac 1 {G(x)}
$$
与前面所推的一致。

如何优雅的求和


$$
\sum _{k = 0} ^n f(k) {n \choose k} c ^k (1-c) ^{n - k}
$$
其中 $f$ 是一个 $m$ 次多项式,输入给出了 $f$ 函数 $0, 1, \cdots, m$ 的点值。$n \le 10 ^9, m \le 10 ^5$。

一个比较直观的思路是直接拆开 $f(k)$ 然后考虑 EGF:
$$
\begin{aligned}
& \sum _{i = 0} ^m a _i \sum _{k = 0} ^n k ^i {n \choose k} c ^k (1 - c) ^{n - k} \\
& \sum _{i \ge 0} \frac {x ^i} {i!} \sum _{k = 0} ^n k ^i {n \choose k} c ^k (1 - c) ^{n - k} \\
=& (ce^x + 1-c) ^n
\end{aligned}
$$
然后我才看到他给的是点值。人傻了……

然后我安慰自己说反正可以插值。但这样显然很难写。

于是我去翻题解。翻到了一个已知点值求下降幂多项式的 trick。具体来说是这样的:
$$
\begin{aligned}
& \sum _{k \ge 0} f (k) \frac {x ^k} {k!} \\
=& \sum _{i = 0} ^m a _i \sum _{k \ge i} k ^{\underline{i}} \frac {x ^k} {k!} \\
=& \sum _{i = 0} ^m a _i \sum _{k \ge i} \frac {x ^k} {(k - i)!} \\
=& e ^x \sum _{i = 0} ^m a _i x ^i
\end{aligned}
$$
所以只需要把点值的 EGF 写出来之后乘上 $e ^{-x}$ 就可以得到下降幂系数了。(貌似这和二项式反演的样子很像?)

有了下降幂之后推原式就很好推了,不写了。