生成函数基础

定义

无穷数列 (<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!})

一些常用的生成函数：

[egin{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} inom c i z^i\ frac{1}{(1-z)^c} &= sum_{i geq 0} inom{c+i-1}{i}z^i\ end{aligned} ]

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

也可以定义二项式定理：((x+y)^{n} = sum_{k geq 0} inom {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 (kln 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) mod (z-x_i))

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

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

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

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

做法 2

某知名 1s 5e5 多点求值

我们平时说的卷积，即 ((+, imes )) 卷积，类比定义减法卷积为 ((-, imes ))，记做 (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) imes 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 eq i}frac{z-x_j}{x_i-x_j})。

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

令 (G(z) = prod_{i=0}^n (z-x_i))。

如果值域连续可以直接做，否则考虑每个点的答案就是 (frac{G(x)}{x-x_i})。上下都是 (0) 考虑洛必达一下，就变成了 (G'(x_i)) 然后多点求值就好了。

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

复合

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

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

类似于 BSGS 那样 取 (M = lceil sqrt n ceil)预处理 (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 + nsqrt n log n))。

复合逆

给定 (F(x))，满足 ([x^0]F(x) = 0,[x^1]F(x) = 1)，求满足 (G(F(z)) = z) 的多项式 (G(z) mod 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(nlog n))。

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

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

[egin{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} ]

于是

[egin{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{inom {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)，那么答案是

[egin{aligned} f_{n+1} &= (v imes A^n)_{1,1}\ &= (v imes R(A))_{1,1}\ &= (v imes sum_{i=0}^{m-1} b_iA^i)_{1,1}\ &= sum_{i=0}^{m-1} b_i imes (v imes 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(egin{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} ight) ]

考虑对第一行展开：

(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)。

[egin{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))。