定义

无穷数列 $<a_0,a_1,a_2,\ldots>$ 的一般生成函数（OGF）是定义在形式幂级数环上的形式幂级数 $A(z)=\sum_{i \geq 0} a_iz^i$，它对应的 指数生成函数（EGF）是 $\hat A(z)=\sum_{i \geq 0} a_i \frac{z^i}{i!}$

一些常用的生成函数：

$$ \begin{aligned} \frac{1}{1-z} &= \sum_{i \geq 0} z^i \\ \ln \frac{1}{1-z} &= \sum_{i > 0}\frac{1}{i}z^i\\ e^z &= \sum_{i \geq 0} \frac{z^i}{i!}\\ (1+z)^c &= \sum_{i \geq 0} \binom c i z^i\\ \frac{1}{(1-z)^c} &= \sum_{i \geq 0} \binom{c+i-1}{i}z^i\\ \end{aligned} $$

需要注意到我们其实是可以在实数上定义组合数的，有$\binom n m = \frac{n^{\underline m}}{m!}$

也可以定义二项式定理：$(x+y)^{n} = \sum_{k \geq 0} \binom {n}{k} x^k y^{n-k}$。

基本操作

加法，乘法等简单运算可见[多项式初步[]]()

牛顿迭代

$x \equiv x_0+\frac{F(x_0)}{F'(x_0)} \pmod {x^{2n}}$

求逆

可以考虑方程 $\frac{1}{x}-F(z)=0$（$x$ 为目标多项式），代入牛顿迭代。

多项式除法/取模

考虑变换 $R_A = x^nA(\frac{1}{x})$，也就是系数翻转。

对数函数

要求常数项为 $1$，求导再积分即可。

指数函数

要求常数项为 $0$，方程 $\ln x - F(z)=0$，牛顿迭代，$x \equiv x_0(1-\ln x_0 + G(z)) \pmod {x^{2n}}$。实际上意义是 $e^{F(x)} = \sum_{i \geq 0}\frac{F(x)^i}{i!}$，有组合意义（图个数 EGF 与连通图个数 EGF 的互相转化）。

求幂

求 $F^k(z) \pmod {z^n}$

如果常数项为 $1$，考虑 $F^k(z) = \exp (k\ln F(z))$，快速计算。

常数项不为 $1$ 时，可以整体乘一个常数项的逆元，

常数项为 $0$ 时，整体平移。

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

多点求值

$n$ 次多项式 $F$，分别求 $F(x_1),F(x_2),\ldots,F(x_m)$。

做法 1

大常数做法，但在某些问题上没有替代性（比如范德蒙德行列式求值）（虽然我也不知道这是个啥 upd at 2020/12/22: 现在我知道这是个啥了）

性质：考虑令 $F(x) = G(x)Q(x)+R(x)$，如果 $G(x) = 0$，那么就会有 $F(x) = R(x)$。

不妨令 $Q(x) = z-x_i$，那么有 $F(x_i) = R(x_i)$，显然 $deg_R < 1$，常数项即为答案。

一句话总结：$F(x_i) = F(z) \bmod (z-x_i)$

考虑多项式还有一个类似于整数取模的性质：$F(x) \bmod kA \bmod A = F(x) \bmod A$，其中$A,k$ 均为多项式。

于是可以考虑分治，我们预先用分治+FFT对于每一个分治结构上的节点对应的区间求出 $\prod_{i=l}^r (z-x_i)$。

假设当前在区间 $[l,r]$，你得到的多项式应该是 $F(x) \bmod \prod_{i=l}^r (z-x_i)$，那么我们递归左边给左边 $\bmod \prod_{i=l}^{mid} (z-x_i)$，递归右边给右边 $\bmod \prod_{i=mid+1}^r (z-x_i)$，递归到最后节点 $[i,i]$ 的常数项就是答案。

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

做法 2

某知名 1s 5e5 多点求值

我们平时说的卷积，即 $(+,\times )$ 卷积，类比定义减法卷积为 $(-,\times )$，记做 $MULT(F(z),G(z)) = \sum_{i \geq 0} \sum_{j \geq 0} (f_{i+j}g_j)z^i$。

则发现 $F(x_i) = [z^0]MULT(F(z),\frac{1}{1-x_iz})$（也就是直接 $[z^j]F(z) \times x_i^j$）。并且不难发现$MULT(F(z),G(z)H(z)) = MULT(MULT(F(z),G(z)),H(z))$，因为 $i-(j+k) = i-j-k$。

于是我们考虑分治，预处理后根节点传入一个 $MULT(F(z),\frac{1}{\prod_{i} (1-x_iz)})$，每次向 $[l,mid]$ 传入 $MULT(F_{[l,r]}(z),\prod_{i=mid+1}^r (1-x_iz))$，$[mid+1,r]$ 类似。

不用写多项式取模，十分快速！

$MULT(F(z),G(z))$ 具体实现可以把 $G$ reverse，变成 $i + (m-j)$ ，最后整体平移就好了。

快速插值

给定 $n+1$ 个点，求一个次数不超过 $n$ 的多项式 $F(x)$。

$n^2$ 暴力是使用拉格朗日插值：$F(z) = \sum_{i=0}^n F(x_i)\prod_{j \neq i}\frac{z-x_j}{x_i-x_j}$。

如果对每个 $i$ 算出 $\prod_{j \neq i}(x_i-x_j)$，就可以分治+FFT 计算。

令 $G(z) = \prod_{i=0}^n (z-x_i)$，可以认为 $G'(x_i) = \prod_{j \neq i} (x_i-x_j)$

分治乘除 $G$ 容易得到 $G'$ 然后多点求值即可。

最后再类似多点求值那样分治求出 $F(z)$ 。

复合

给定 $F(z),G(z)$，求 $F(G(z)) \bmod z^n$（$G$ 常数项为 $0$）

展开：$\sum_{i=0}^{n-1} f_iG^i(z) \pmod {z^n}$

类似于 BSGS 那样 取 $M = \lceil \sqrt n \rceil$预处理 $G(z),G^2(z),\ldots,G^M(z),G^{2M}(z),\ldots,G^{M^2}(z) \pmod {z^n}$，先都 DFT 一下，然后按照定义计算，最后加起来 IDFT 回去即可。$I(n^2 + n\sqrt n \log n)$。

复合逆

给定 $F(x)$，满足 $[x^0]F(x) = 0,[x^1]F(x) = 1$，求满足 $G(F(z)) = z$ 的多项式 $G(z) \bmod z$。等价于 $F(G(z)) =z $。

如果直接按照定义牛顿迭代：$F(x)-z = 0$

$x \equiv x_0 - \frac{F(x_0)-z}{F'(x_0)} \pmod {z^{2n}}$，复杂度与计算复合$ F(x)$ 相同。

如果只要求一项的话 可以用拉格朗日反演做到优秀的复杂度。

拉格朗日反演：若 $F(x) = z$，则

$$ [z^n]x = \frac{1}{n}[w^{n-1}](\frac{w}{F(w)})^n $$

$$ [z^n]H(x)=\frac{1}{n}[w^{n-1}]H'(w)(\frac{w}{F(w)})^n $$

可以 $O(n\log n)$。

小应用：$n$ 个点的二叉树计数。

OGF是 $F(z) = z(1+F(z))^2$，现在想求复合逆 $G(z)$。

$$ \begin{aligned} F(G(z)) &= z\\ &= G(z)(1+F(G(z)))^2\\ &= G(z)(1+z)^2\\ \Rightarrow G(z) &= \frac{z}{(1+z)^2} \end{aligned} $$

于是

$$ \begin{aligned} [z^n]F(z) &= \frac{1}{n}[w^{n-1}](\frac{w}{G(w)})^n\\ &= \frac{1}{n}[w^{n-1}](\frac{w}{\frac{w}{(1+w)^2}})^n\\ &= \frac{1}{n}[w^{n-1}](1+w)^{2n}\\ &= \frac{\binom {2n} {n-1}}{n} \end{aligned} $$

$k$ 叉树也能这么做。

特别应用：考虑在特殊的二元生成函数上做一个拉格朗日反演

$$[z^n]\frac{1}{1-uF(z)}=\frac{1}{n}[w^{n-1}](\frac{1}{1-uw})' (\frac{w}{F^{-1}(w)})^n$$
当 $F^{-1}(w)$ 可以快速求得时，这个式子可以 $O(n \log n)$ 计算。
简单运用：求 $[z^n]F(z),[z^n]F^2(z),\ldots,[z^n]F^n(z),$
相当于计算 $[z^n]\frac{1}{1-uF(z)}$ 当 $F(z)$ 有复合逆的时候可以快速计算（其实维护二元生成函数也不是很快）

常系数线性递推

设初始值分别为 $f_0,f_1,\ldots,f_{m-1}$

设 $A$ 为转移矩阵，考虑我们实际上是想快速求出 $A^n$

根据 Hamilton-Cayley theorem ，设 $f(\lambda)$ 为$A$ 的特征多项式（即 $f(\lambda) = |\lambda I-A|$ 可以得到 $f(A) = 0$

考虑多项式 $x^n$ 对 $f(x)$ 取模，得到 $x^n = f(x)Q(x)+R(x)$，代入 $x=A$，得到 $A^n = R(A)$。

如果设初始向量为 $\vec a$，那么答案是

$$ \begin{aligned} f_{n+1} &= (v \times A^n)_{1,1}\\ &= (v \times R(A))_{1,1}\\ &= (v \times \sum_{i=0}^{m-1} b_iA^i)_{1,1}\\ &= \sum_{i=0}^{m-1} b_i \times (v \times A^i)_{1,1}\\ &= \sum_{i=0}^{m-1} a_{i+1}b_i \end{aligned} $$

最后一个问题是如何得到特征多项式。如果设转移系数为 $g_0,g_1,\ldots,g_{m-1}$，写出矩阵：

$$ A=\left(\begin{matrix} \lambda-g_0 & -g_1 & -g_2 & \cdots & -g_{k-3} & -g_{k-2} & -g_{k-1}\\ -1 & \lambda & 0 & \cdots & 0 & 0&0 \\ 0 & -1 & \lambda & \cdots & 0 & 0&0\\ \vdots & \vdots & \vdots & \ddots &\vdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & -1 & \lambda & 0\\ 0 & 0 & 0 & \vdots & 0 & -1 & \lambda \end{matrix}\right) $$

考虑对第一行展开：

$f(\lambda) = A_{1,1}(\lambda-g_0)-a_2A_{1,2}-\ldots-a_kA_{1,k}$

其中 $A_{i,j}$ 表示 $i$ 行 $j$ 列的代数余子式。

最终可以得到 $f(\lambda) = \lambda^k-\sum_{i=0}^{k-1} g_i \lambda^{k-i-1}$。

倍增+多项式取模，$O(n \log n \log k)$

题目

持续更新中...

真实无妄她们的人生之路

题目链接

先考虑如果不拿走咋做：设$f_{i,j}$ 表示考虑了前 $i$ 个物品，等级为 $j$ 的概率，转移是 $f_{i,j} = p_if_{i-1,j-1}+(1-p_i)f_{i-1,j}$

设 $F_i(z)$ 表示 $f_i$ 的生成函数，转移可以写成 $F_i(z) = p_iF_{i-1}(z)z+(1-p_i)F_{i-1}(z)$，其中 $F_0(z) = 1$。

$$ \begin{aligned} F_i(z) &= F_{i-1}(z)(p_iz+1-p_i)\\ &= \prod_{j=1}^i (p_iz+1-p_i) \end{aligned} $$

那么答案的生成函数就是 $F(z) = MUL(F_n(z),\sum_{i=0}^{n-1}a_ix^i)$。

删掉第 $i$ 个物品的生成函数是 $G_i(z) = MUL(\frac{F_n(z)}{p_iz+1-p_i},\sum_{i=0}^{n-1}a_ix^i)$。

发现 $MUL(AB,C) = MUL(A,C)B$，因为 $i+j-k = i-k+j$。

所以相当于就是求第 $i$ 个位置除一个二项式后的多项式的 $z^0$ 的系数。

类似多点求值，写一个分治：预处理每个节点的 $\prod_{i=l}^r (p_iz+1-p_i)$。最初传入 $\frac{F}{\prod_{i-1}^n (p_iz+1-p_i)}$，每次将右边的多项式乘到左边，左边的多项式乘到右边。时间复杂度 $O(n \log^2 n)$。