Part 1 前言
生成函数的变换是把一个生成函数变成另一个生成函数的一些式子,这些式子往往具有某种组合意义。
在本文中,我们讨论的是球盒模型,即统计在若干个盒子中放 n 个小球的方案数的问题。
Part 2 一些约定
- F(x)=i=0∑∞fixi,G(x)=i=0∑∞fii!xi:参与变换的生成函数,即 fi 的 OGF 与 EGF,fi 的意义是有 fi 种方式把 i 个球放进同一个盒子中;
- 一般认为 f0=0,即不能存在空盒子;
- [xn]H(x):若 H(x) 为 OGF,则代表 H(x) 中 xn 的系数;若 H(x) 为 EGF,则代表 H(x) 中 n!xn 的系数。简单的说就是我们要求的答案;
Part 3 各种生成函数的变换
球无标号,盒有标号:不知道叫什么变换
最简单,根据 OGF 乘法的定义,枚举球一共占用了多少个盒子,有:
???(F(x))=i=0∑∞F(x)i=1−F(x)1
球有标号,盒有标号:Invert 变换
也可以叫 SEQ 变换。
根据 EGF 乘法的定义,枚举球一共占用了多少个盒子,有:
Invert(G(x))=i=0∑∞G(x)i=1−G(x)1
球有标号,盒无标号:Exp 变换
根据 EGF 乘法的定义,枚举球一共占用了多少个盒子,但这样盒子是有标号的。注意到每种标号方式都会被算到恰好一次,所以要除掉盒子个数的阶乘:
Exp(G(x))=i=0∑∞i!G(x)i=exp(G(x))
球无标号,盒无标号:Weigh&Euler 变换
Weigh 变换
放的球一样多,放球的方式也一样的盒子只能出现一次。
类似 01 背包,放 i 个球的盒子有 fi 种,每种只能出现一次,那么有:
Weigh(F(x))=i=0∏∞(1+xi)fi
即枚举盒子大小,然后因为有 fi 种这样的盒子所以要乘那么多次 1+xi。
这个东西不好化简,考虑 ln 再 exp,要注意 ln(1+x)=−i=1∑∞i!(−1)i(i−1)!xi=−i=1∑∞i(−x)i:
ln(Weigh(F(x)))=i=0∑∞filn(1+xi)=−i=0∑∞fij=1∑∞j(−xi)j=−i=1∑∞i(−1)ij=0∑∞fjxij=−i=1∑∞i(−1)iF(xi)
那么:
Weigh(F(x))=exp(−i=1∑∞i(−1)iF(xi))
Euler 变换
无限制。
类似 Weigh,大小和放球方式都相同的盒子一起处理,相当于处理排序后的盒子。同种盒子允许有任意个可以通过套一层 Invert 变换来实现:
E(F(x))=i=0∏∞(1−xi1)fi
同样是 ln 再 exp:
ln(E(F(x)))=i=0∑∞filn(1−xi1)=−i=0∑∞filn(1−xi)=i=0∑∞fij=1∑∞jxij=i=1∑∞iF(xi)
所以:
E(F(x))=exp(i=1∑∞iF(xi))
复合变换
考虑另一个 OGF H(x)=i=0∑∞hixi,考虑复合函数 H(F(x)) 和 H(G(x)) 的意义:
- [xn]H(F(x))=[xn]i=0∑∞hiF(x)i:n 个无标号小球放入若干个有标号盒子中,每个盒子放 i 个小球均有 [xi]F(x) 种方案。这若干个盒子放入一个大箱子中,大箱子中放 i 个盒子有 hi 种方案;
- [xn]H(G(x))=[xn]i=0∑∞hiG(x)i:n 个有标号小球放入若干个有标号盒子中,每个盒子放 i 个小球均有 [xi]G(x) 种方案。这若干个盒子放入一个大箱子中,大箱子中放 i 个盒子有 hi 种方案;
注意 H(x) 也可以是 EGF,并且可以复合再复合。
比较经典的是有标号有根树的 EGF T(x) 复合上任意生成函数。
Part 4 各种变换的计算
-
???(x) 和 Invert(x):求逆即可;
-
Exp(x):直接多项式 exp;
-
Weigh(x) 和 E(x):暴力调和级数;
-
复合变换:
牛顿迭代。以有标号有根树的 EGF T(x)=1+i=1∑∞ii−1i!xi 为例,考虑另一个生成函数 H(x)(不管是 OGF 还是 EGF),求解 T(H(x))。
显然有 T(x)=xexp(T(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) 的偏导,即把 A(x) 外的东西都看作常数,所以有:P′(A(x))=1−H(x)exp(A(x))。
那么牛顿迭代求解即可。
求出来 T(H(x)) 后可以 O(n) 算出有标号无根树复合 H(x) 的结果,这样就可以算点双边双什么的了。
Part 5 拓展应用
无标号有根树计数
设无标号有根树个数的 OGF 为 T(x),那么显然有 T(x)=xE(T(x))=xexp(i=1∑∞iT(xi))。那么构造 P(T(x))=ln(xT(x))−i=1∑∞iT(xi)。
注意到牛迭的前提是已知 T∗(x)≡T(x)(modx2n),要求 P′(T∗(x))P(T∗(x))(modxn)。那么显然 B(x)=i≥2∑∞iT∗(xi)modxn 是已知的,则有:
P(T∗(x))≡ln(xT∗(x))−T∗(x)−B(x)(modxn)P′(T∗(x))≡T∗(x)1−T∗(x)(modxn)
发现 [x0]T∗(x)=0,直接牛迭会解出 0,所以考虑用牛迭求解 A(x)=xT(x):
P(A∗(x))≡ln(A∗(x))−xA∗(x)−B(x)(modxn)P′(A∗(x))≡A∗(x)1−x(modxn)
注意到 B(x) 可以在倍增的时候动态调和级数维护,所以 ln 加上两次求逆,再动态维护 B(x) 即可。
时间复杂度 O(nlogn),常数略大。
这个东西变成无根也很简单,只要减掉根不是重心的情况即可。