Generating function

public 学习笔记 Comments

生成函数定义：

一般生成函数（OGF）

一般用于处理组合问题（无标号）

$F(x)=\sum_{i=0}^{\infty}f_ix^i$

OGF的运算

假设现在有两类组合对象$A,B$

首先考虑如何对它们取并

显然对于一个元素$t$，在$A$中出现了$a_t$次，在$B$中出现了$b_t$次，一共会出现$a_t+b_t$次

记为$C(x)=A(x)+B(x)$

那么对应标号的系数相加即可

然后考虑如何求它们的笛卡尔积

假设$A,B$笛卡尔积为$C$，那么表示$C$中每个元素$c$都是由$A$中的一个元素$a$和$B$中的一个元素$b$拼成的二元组$(a,b),|c|=|a|+|b|$

记为$C(x)=A(x)B(x)$

在生成函数为有限项的时候用$FFT/NTT$多项式乘法即可

OGF生成序列

现在有一类组合对象$A$，定义$seq(A)$ 是由$A$的元素排列成的序列组成的集
合，一个序列的大小定义为其元素大小总和。
$eg1:A=\{“0”,”1”\}$，$seq(A)=\{all\ 01\ string\}$
$eg2:N^\times=\{1,2,3,…\}$，元素的大小定义为它的数值，则$seq(N)=\{正整数的有序拆分\}$
规定A 中不含大小为0 的元素，则
$seq(A)=1+A+A^2+A^3+…=\frac1{1-A}$

指数生成函数(EGF)

一般用于处理组合问题（有标号）
常见带标号的组合对象：标号图，置换
将两个元素$a,b$拼接起来，$|a|=n,|b|=m$
无标号时，只有一种方法；
带标号时，规定拼接时拼接对象内部相对标号顺序不变，而互相的标号
可以改变，则有$\frac{(n+m)!}{n!m!}=C_{n+m}^n$种方法

$F(x)=\sum_{i=0}^{\infty}f_i\frac{x^i}{i!}$

EGF的运算

并集：$C(x)=A(x)+B(x)$
笛卡尔积：$C(x)=A(x)B(x)$
对比系数后很好理解

EGF生成序列

同$OGF$，$seq(A)=\frac1{1-A}$

EGF生成集合

集合与序列的区别：同样由$i$个$EGF$生成，集合的顺序不重要，序列的顺序确实确定的。
因此由$i$个$EGF$生成的集合应该有一个$\frac1{i!}$的系数。
$set(A)=\sum_{i=0}^{\infty}\frac{A^i}{i!}=e^{A}$

生成函数计数

置换计数

一个置换是由若干轮换组成的集合。
$k$轮换的个数有$(k-1)!$个，对应$EGF$为$(k-1)!\frac{x^k}{k!}=\frac{x^k}k$
于是全体轮换的$EGF=\sum_{i=0}^{\infty}\frac{x^k}k$
设$f(x)=\sum_{i=0}^{\infty}\frac{x^k}k$
那么$f’(x)=\sum_{i=0}^{\infty}x^k=\frac1{1-x}$
那么$f(x)=\int f’(x)\,dx=\int\frac1{1-x}\,dx=-\ln(1-x)$
根据定义，全体置换的$EGF$为$e^{f(x)}=e^{-\ln(1-x)}=\frac1{1-x}$
这样看来，$k$置换的个数有$k!$个符合事实。
如果限制每个轮换的大小都在集合$S$内呢？
那么可生成置换的$EGF=e^{\sum_{k\in S}\frac{x^k}k}$

多项式$exp$即可

背包计数

  1. 有$\sum_{i=1}^na_i$种物品，体积为$i$的物品有$a_i$种，每种物品有无限个。
  2. 有$\sum_{i=1}^na_i$种物品，体积为$i$的物品有$a_i$种，每种物品有无限个。
  3. 有$n$种物品，第$i$种物品体积为$i$，第$i$种物品有$a_i$个。

对于所有$1\le i\le n$，回答选取物品体积为$i$的方案数。

均可在$O(n\log n)$的时间内求解。

Q1

体积为$i$的物品的生成函数为$\sum_{j=0}^{\infty}(x^i)^j=1+x^i+x^{2i}+\cdot\cdot\cdot$
那么答案的生成函数为$F(x)=\prod_{i=1}^n(1+x^i+x^{2i}+\cdot\cdot\cdot)^{a_i}=\prod_{i=1}^n(\frac1{1-x^i})^{a_i}$

构造生成函数$A(x)=\sum_{i=1}^na_ix^i$

考虑用$ln$和$exp$转化。

$A(x^j)$中只有$\left\lfloor\frac nj\right\rfloor$项有贡献。
所以暴力调和计数算出幂对应的多项式然后加一个多项式$exp$即可。
复杂度$O(n\log n)$

Q2

同$Q1$处理即可。

Q3

$A(x^j),B(x^j)$中只有$\left\lfloor\frac nj\right\rfloor$项有贡献。
于是同$Q1,2$处理即可。

树的计数

求$n$个点的树的个数。

有标号无根树计数

利用$prufer$数列可以知道答案为$n^{n-2}$

有标号有根树计数

先生成有标号无根树，然后有$n$种方案选出根节点，答案为$n^{n-2}\times n=n^{n-1}$

无标号有根树计数

我们设出答案的生成函数$F(x)=\sum_{i=0}^{\infty}f_ix^i$，那么$f_i$对应$i$个点的答案。
现在假设已经推出$f_{1,2,3,…,n}$，要推$f_{n+1}$。

考虑到$n+1$个点的有根树相当于$n$个点的森林加上一个根。
那么我们只需要求出$n$个点森林的方案数。

由于点无标号，因此相同大小的树之间没有顺序，我们应当按照树的大小归类分别求出其生成函数然后来拼接这个森林。

由于大小为$k$的树对应的生成函数为$\sum\limits_{i}x^{ik}=\frac1{1-x^k}$
所以所有大小为$k$的树形成森林的生成函数为$c$

那么$F(x)=x\prod\limits_{i=1}^{\infty}(\frac1{1-x^i})^{f_i}$

果断上多项式取对：

考虑令$g_n=\sum_{i|n}f_ii$
那么$f_n=\frac{\sum_{i=1}^{n-1}f_ig_{n-i}}{n-1}$
于是可以分治$fft$处理$f$，枚举倍数更新$g$。
时间复杂度$O(n\log^2n)$

无标号无根树计数

你需要计算出有根树的答案，然后去世容斥。
记$n$个点答案为$h_n$。

发现只有根节点是树的质心时我们才计算的话就不会算重。

若一个根不为质心，那么有且仅有一个子树大小大于$\left\lfloor\frac n2\right\rfloor$，考虑容斥掉这些不合法的。
然后要按$n$的奇偶性分类讨论一波：

  1. $n$为奇数：
    $h_n=f_n-\sum\limits_{i=1}^{\left\lfloor\frac{n}2\right\rfloor}f_if_{n-i}$
  2. $n$为偶数：
    此时可能存在两个质心，因此枚举到$i=\frac n2$时只能减去两边不一样的情况，即$h_n=f_n-\sum\limits_{i=1}^{\frac{n}2-1}f_if_{n-i}-\binom{f_\frac n2}2$

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

概率生成函数

对于一个随机离散变量 $X$ ，我们定义其概率生成函数 $f(z)=\mathbb{E}(z^{X})=\sum\limits_{i=0}^{+\infty}Pr(X=i)z^i$

不难发现以下性质：

对于掷骰子的问题我们一般用以下几种关系来建立等式：

设时刻 $i$ 结束的概率生成函数为 $F(x)$ ， 未结束的概率生成函数为 $G(x)$

那么

然后对第一个式子求导，对第二个等式带入 $x=1$ 即可

例题：[CTSC2006]歌唱王国,hdu4652

而在有多个终态的时候一般考虑如下方法变形：

  1. $min-max$ 容斥
  2. 利用 $\sum\limits_{i}F_i(1)=1$这个等式和之前的等式建立方程组跑高斯消元解方程

例题：[SDOI2017]硬币游戏

ldxcaicaia loser😬😦😭😢😰

Glory is just in sight.