生成函数变换学习笔记

Part 1 前言

生成函数的变换是把一个生成函数变成另一个生成函数的一些式子,这些式子往往具有某种组合意义。

在本文中,我们讨论的是球盒模型,即统计在若干个盒子nn 个小球的方案数的问题。

Part 2 一些约定

  • F(x)=i=0fixiF(x)=\sum\limits_{i=0}^\infin f_ix^iG(x)=i=0fixii!G(x)=\sum\limits_{i=0}^\infin f_i\frac{x^i}{i!}:参与变换的生成函数,即 fif_i 的 OGF 与 EGF,fif_i 的意义是有 fif_i 种方式把 ii 个球放进同一个盒子中;
  • 一般认为 f0=0f_0=0,即不能存在空盒子;
  • [xn]H(x)[x^n]H(x):若 H(x)H(x) 为 OGF,则代表 H(x)H(x)xnx^n 的系数;若 H(x)H(x) 为 EGF,则代表 H(x)H(x)xnn!\frac{x^n}{n!} 的系数。简单的说就是我们要求的答案;

Part 3 各种生成函数的变换

球无标号,盒有标号:不知道叫什么变换

最简单,根据 OGF 乘法的定义,枚举球一共占用了多少个盒子,有:

???(F(x))=i=0F(x)i=11F(x)\begin{aligned} \operatorname{???}(F(x))&=\sum\limits_{i=0}^\infin F(x)^i\\ &=\frac{1}{1-F(x)} \end{aligned}

球有标号,盒有标号:Invert\operatorname{Invert} 变换

也可以叫 SEQ\operatorname{SEQ} 变换。

根据 EGF 乘法的定义,枚举球一共占用了多少个盒子,有:

Invert(G(x))=i=0G(x)i=11G(x)\begin{aligned} \operatorname{Invert}(G(x))&=\sum\limits_{i=0}^\infin G(x)^i\\ &=\frac{1}{1-G(x)} \end{aligned}

球有标号,盒无标号:Exp\operatorname{Exp} 变换

根据 EGF 乘法的定义,枚举球一共占用了多少个盒子,但这样盒子是有标号的。注意到每种标号方式都会被算到恰好一次,所以要除掉盒子个数的阶乘:

Exp(G(x))=i=0G(x)ii!=exp(G(x))\begin{aligned} \operatorname{Exp}(G(x))&=\sum\limits_{i=0}^\infin \frac{G(x)^i}{i!}\\ &=\exp(G(x)) \end{aligned}

球无标号,盒无标号:Weigh&Euler\operatorname{Weigh}\&\operatorname{Euler} 变换

Weigh\operatorname{Weigh} 变换

放的球一样多,放球的方式也一样的盒子只能出现一次。

类似 0101 背包,放 ii 个球的盒子有 fif_i 种,每种只能出现一次,那么有:

Weigh(F(x))=i=0(1+xi)fi\operatorname{Weigh}(F(x))=\prod\limits_{i=0}^\infin (1+x^i)^{f_i}\\

即枚举盒子大小,然后因为有 fif_i 种这样的盒子所以要乘那么多次 1+xi1+x^i

这个东西不好化简,考虑 ln\lnexp\exp,要注意 ln(1+x)=i=1(1)i(i1)!xii!=i=1(x)ii\ln(1+x)=-\sum\limits_{i=1}^\infin\frac{(-1)^{i}(i-1)!x^i}{i!}=-\sum\limits_{i=1}^\infin\frac{(-x)^i}{i}

ln(Weigh(F(x)))=i=0filn(1+xi)=i=0fij=1(xi)jj=i=1(1)iij=0fjxij=i=1(1)iiF(xi)\begin{aligned} \ln(\operatorname{Weigh}(F(x)))&=\sum\limits_{i=0}^\infin f_i\ln(1+x^i)\\ &=-\sum\limits_{i=0}^\infin f_i\sum\limits_{j=1}^\infin\frac{(-x^i)^j}{j}\\ &=-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}\sum\limits_{j=0}^\infin f_jx^{ij}\\ &=-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}F(x^i)\\ \end{aligned}

那么:

Weigh(F(x))=exp(i=1(1)iiF(xi))\operatorname{Weigh}(F(x))=\exp\left(-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}F(x^i)\right)

Euler\operatorname{Euler} 变换

无限制。

类似 Weigh,大小和放球方式都相同的盒子一起处理,相当于处理排序后的盒子。同种盒子允许有任意个可以通过套一层 Invert 变换来实现:

E(F(x))=i=0(11xi)fi\mathcal{E}(F(x))=\prod\limits_{i=0}^\infin \left(\frac{1}{1-x^i}\right)^{f_i}\\

同样是 ln\lnexp\exp

ln(E(F(x)))=i=0filn(11xi)=i=0filn(1xi)=i=0fij=1xijj=i=1F(xi)i\begin{aligned} \ln(\mathcal{E}(F(x)))&=\sum\limits_{i=0}^\infin f_i\ln\left(\frac{1}{1-x^i}\right)\\ &=-\sum\limits_{i=0}^\infin f_i\ln(1-x^i)\\ &=\sum\limits_{i=0}^\infin f_i\sum\limits_{j=1}^\infin\frac{x^{ij}}{j}\\ &=\sum\limits_{i=1}^\infin \frac{F(x^i)}{i} \end{aligned}

所以:

E(F(x))=exp(i=1F(xi)i)\mathcal{E}(F(x))=\exp\left(\sum\limits_{i=1}^\infin \frac{F(x^i)}{i}\right)

复合变换

考虑另一个 OGF H(x)=i=0hixiH(x)=\sum\limits_{i=0}^\infin h_ix^i,考虑复合函数 H(F(x))H(F(x))H(G(x))H(G(x)) 的意义:

  • [xn]H(F(x))=[xn]i=0hiF(x)i[x^n]H(F(x))=[x^n]\sum\limits_{i=0}^\infin h_iF(x)^inn无标号小球放入若干个有标号盒子中,每个盒子放 ii 个小球均有 [xi]F(x)[x^i]F(x) 种方案。这若干个盒子放入一个大箱子中,大箱子中放 ii 个盒子有 hih_i 种方案;
  • [xn]H(G(x))=[xn]i=0hiG(x)i[x^n]H(G(x))=[x^n]\sum\limits_{i=0}^\infin h_iG(x)^inn有标号小球放入若干个有标号盒子中,每个盒子放 ii 个小球均有 [xi]G(x)[x^i]G(x) 种方案。这若干个盒子放入一个大箱子中,大箱子中放 ii 个盒子有 hih_i 种方案;

注意 H(x)H(x) 也可以是 EGF,并且可以复合再复合。

比较经典的是有标号有根树的 EGF T(x)T(x) 复合上任意生成函数。

Part 4 各种变换的计算

  • ???(x)\operatorname{???}(x)Invert(x)\operatorname{Invert}(x):求逆即可;

  • Exp(x)\operatorname{Exp}(x):直接多项式 exp;

  • Weigh(x)\operatorname{Weigh}(x)E(x)\mathcal{E}(x):暴力调和级数;

  • 复合变换:

    牛顿迭代。以有标号有根树的 EGF T(x)=1+i=1ii1xii!T(x)=1+\sum\limits_{i=1}^\infin i^{i-1}\frac{x^i}{i!} 为例,考虑另一个生成函数 H(x)H(x)(不管是 OGF 还是 EGF),求解 T(H(x))T(H(x))

    显然有 T(x)=xexp(T(x))T(x)=x\exp(T(x)),那么有 T(H(x))=H(x)exp(T(H(x)))T(H(x))=H(x)\exp(T(H(x)))

    根据牛迭式子,构造 P(A(x))=A(x)H(x)exp(A(x))P(A(x))=A(x)-H(x)\exp(A(x))

    P(A(x))P(A(x)) 很好算,但是求导的时候要注意实际上求的是关于 A(x)A(x) 的偏导,即把 A(x)A(x) 外的东西都看作常数,所以有:P(A(x))=1H(x)exp(A(x))P'(A(x))=1-H(x)\exp(A(x))

    那么牛顿迭代求解即可。

    求出来 T(H(x))T(H(x)) 后可以 O(n)O(n) 算出有标号无根树复合 H(x)H(x) 的结果,这样就可以算点双边双什么的了。

Part 5 拓展应用

无标号有根树计数

设无标号有根树个数的 OGF 为 T(x)T(x),那么显然有 T(x)=xE(T(x))=xexp(i=1T(xi)i)T(x)=x\mathcal{E}(T(x))=x\exp\left(\sum\limits_{i=1}^\infin \frac{T(x^i)}{i}\right)。那么构造 P(T(x))=ln(T(x)x)i=1T(xi)iP(T(x))=\ln\left(\frac{T(x)}{x}\right)-\sum\limits_{i=1}^\infin \frac{T(x^i)}{i}

注意到牛迭的前提是已知 T(x)T(x)(modxn2)T_*(x)\equiv T(x)\pmod{x^\frac{n}{2}},要求 P(T(x))P(T(x))(modxn)\frac{P(T_*(x))}{P'(T_*(x))}\pmod{x^n}。那么显然 B(x)=i2T(xi)imodxnB(x)=\sum\limits_{i\ge 2}^\infin \frac{T_*(x^i)}{i}\mod{x^n} 是已知的,则有:

P(T(x))ln(T(x)x)T(x)B(x)(modxn)P(T(x))1T(x)T(x)(modxn)P(T_*(x))\equiv \ln\left(\frac{T_*(x)}{x}\right)-T_*(x)-B(x)\pmod{x^n}\\ P'(T_*(x))\equiv \frac{1}{T_*(x)}-T_*(x)\pmod{x^n}\\

发现 [x0]T(x)=0[x^0]T_*(x)=0,直接牛迭会解出 00,所以考虑用牛迭求解 A(x)=T(x)xA(x)=\frac{T(x)}{x}

P(A(x))ln(A(x))xA(x)B(x)(modxn)P(A(x))1A(x)x(modxn)P(A_*(x))\equiv \ln\left(A_*(x)\right)-xA_*(x)-B(x)\pmod{x^n}\\ P'(A_*(x))\equiv \frac{1}{A_*(x)}-x\pmod{x^n}\\

注意到 B(x)B(x) 可以在倍增的时候动态调和级数维护,所以 ln\ln 加上两次求逆,再动态维护 B(x)B(x) 即可。

时间复杂度 O(nlogn)O(n\log n),常数略大。

这个东西变成无根也很简单,只要减掉根不是重心的情况即可。