注意日期!别人情人节在和girlfriend亲亲，我呢在和generating function亲亲……
这篇学习笔记不打算从头开始讲什么是GF，只说一些简单的trick。
约定 :
我们使用球和盒子的模型来考虑问题，也就是说数列\(f\)的组合意义被认为是 : 我们现在要往盒子\(f\)里放一些球然后涂色，\(f_n\)表示在放\(n\)个球之后有\(f_n\)种涂色方案。
因为我太懒，所以EGF不会加\hat。
简单组合变换
这一段是_rqy课件的学习笔记(不过我看吐了，只能写简单的东西了)。
有很多生成函数操作可以归结到一些经典的组合变换上来。
具体地，现在我们知道往一个盒子里放球的方案数的生成函数\(G\)，要求往一些盒子里放球的方案数的生成函数\(F\)。这个从\(F\)到\(G\)的变换\(F=f(G)\)就是一个组合变换。rqy的课件中提到了三十六种组合变换，但是讲了式子的只有十种左右，而我只看懂了四种，实在是太拉了。
Invert
这个东西是最简单的了!
球有标号，盒子有标号，没有额外限制。
根据幂的组合意义，枚举放了多少个盒子，容易得到
\[F=G+G^2+G^3+...=\frac{1}{1-G}\]这就是Invert变换。这个东西也被称为SEQ。
Exp
球有标号，盒子无标号，没有额外限制。
实际上就是Invert去掉盒子的标号，发现对于球有标号的情况，去掉盒子的标号其实就是除掉排列盒子的方案数——也就是盒子数量的阶乘，得到
\[F=\sum_{i=1}^{\infty}\frac{G^i}{i!}=\exp G\]Weigh
球无标号，盒子无标号，不能出现两个大小颜色都相同的盒子。
考虑这相当于对每种大小颜色的盒子做一个01背包，相当于把一堆\(1+z^k\)卷起来。
然后对于同一大小不同颜色的盒子，每种颜色卷进来的东西是一样的，那么枚举大小容易得到
\[F=\prod_{i=1}^{\infty}(1+z^i)^{g_i}\]这个式子，因为有\(g_i\)这种东西，好像不够优美?看到\(\prod\)和指数上的\(g_i\)，我们用\(\ln\)来变个魔术。
\[\begin{aligned} F&=\prod_{i=1}^{\infty}(1+z^i)^{g_i}\\ \ln F&=\sum_{i=1}^{\infty}\ln(1+z^i)^{g_i}\\ &=-\sum_{i=1}^{\infty}g_i\sum_{j=1}^{\infty}\frac{(-z^i)^j}{j}\\ &=-\sum_{i=1}^{\infty}g_i\sum_{j=1}^{\infty}\frac{(-1)^jz^{ij}}{j}\\ &=-\sum_{j=1}^{\infty}\frac{(-1)^j}{j}\sum_{i=1}^{\infty}g_iz_{ij}\\ F&=\exp \sum_{j=1}^{\infty}\frac{(-1)^{j+1}}{j}G(z^j) \end{aligned}\](注意这个推导中的负号!)
Euler
球无标号，盒子无标号，没有额外限制。
Weigh变换是01背包，Euler变换是完全背包。我们要把一堆\(1+z^k+z^{2k}+...=\frac{1}{1-z^k}\)卷起来，与Weigh变换类似可以得到
\[F=\prod_{i=1}^{\infty}(\frac{1}{1-z^i})^g_i\]然后同样用\(\ln\)变魔术
\[\begin{aligned} \ln\frac{1}{1-x}&=-\ln1-x\\ F&=\prod_{i=1}^{\infty}(\frac{1}{1-z^i})^{g_i}\\ \ln F&=\sum_{i=1}^{\infty}g_i\sum_{j=1}^{\infty}\frac{z^{ij}}{j}\\ &=\sum_{j=1}^{\infty}\frac{1}{j}\sum_{i=1}^{\infty}z^{ij}g_i\\ &=\sum_{j=1}^{\infty}\frac{G(z^j)}{j}\\ F&=\exp\sum_{j=1}^{\infty}\frac{G(z^j)}{j} \end{aligned}\]注意消去的负号。
Euler变换有个记号，比如上面的结果可以记为\(F=\mathcal{E}(G)\)。打法是\mathcal{E}。
这个东西也被称为MSET，或者Polya Exp。
计算简单组合变换
Invert和Exp广为人知了。
Euler变换可以直接求出那个\(\sum\)然后\(\exp\)，第一部分的复杂度是调和数的\(O(n\log n)\)，这个题好像是 付公主的背包。Weigh同理。
牛迭
首先牛顿迭代是什么大家都知道，总而言之就是 : 有一个定义域是形式幂级数的函数\(f\)，现在要求解\(f(F(z))=0\)。可以考虑倍增，假设我们已经求出\(f(F_0(z))\equiv 0\pmod{z^k}\)，现在想求\(f(F(z))\equiv 0\pmod{z^{2k}}\)的\(F\)，我们可以把\(f(F)\)在\(F_0\)这个点泰勒展开，
\[f(F)=\sum_{i=0}^{\infty}\frac{f^{(i)}(F_0)}{i!}(F-F_0)^i\]然后推一波柿子 :
\[\begin{aligned} f(F)&\equiv 0\pmod{z^{2k}}\\ \sum_{i=0}^{\infty}\frac{f^{(i)}(F_0)}{i!}(F-F_0)^i&\equiv 0\\ f(F_0)+f^{\prime}(F_0)(F-F_0)+f^{\prime}(F_0)(F-F_0)^2+\dots&\equiv 0 \end{aligned}\]接下来你发现，\(F\)和\(F_0\)的前\(k\)项肯定是相同的，那么\(F-F_0\)的前\(k\)项全是\(0\)，那么\((F-F_0)^2\)的前\(2k\)项应该也都是0(这个可以自己把卷积的式子写出来看一看)，所以这些项都被\(z^{2k}\)给膜没了!接下来的式子就很简单了。
\[\begin{aligned} f(F_0)+f^{\prime}(F_0)(F-F_0)&\equiv 0\\ f(F_0)+f^{\prime}(F_0)F-f^{\prime}(F_0)F_0&\equiv 0\\ F&\equiv \frac{f^{\prime}(F_0)F_0-f(F_0)}{f^{\prime}(F_0)}\equiv F_0-\frac{f(F_0)}{f^{\prime}(F_0)} \end{aligned}\]然后我们就得到了一个带项式牛顿迭代公式。这个东西可以干什么呢?用来跑不过多叉分治
\(\exp\)
要求\(F=\exp G\)，相当于\(\ln F-G=0\)，那么我们设\(f(F)=\ln F-G\)。然后看看这个复合，发现\(f(F_0)\)很好说，但是这个\(f^{\prime}(F_0)\)怎么求呢?
实际上，我们这里的导数，因为是在\(F_0\)处泰勒展开，求的应该是\(\frac{df(F)}{dF}\)而不是\(\frac{df(F(z))}{dz}\)，所以求导的时候那个\(G\)就没了。\(f^{\prime}(F_0)=\frac{1}{F_0}\)。
所以代入我们的迭代公式就得到\(F\equiv F_0-F_0(\ln F_0-G)\pmod{z^{2k}}\)。
开根
要求\(F=\sqrt{G}\)，相当于\(F^2-G=0\)，那么我们设\(f(F)=\ln F-G\)。然后看看这个复合，发现\(f(F_0)\)很好说，\(f^{\prime}(F_0)\)也很好说，它就是\(2F\)。
所以代入我们的迭代公式就得到\(F\equiv F_0-\frac{F_0^2-G}{2F_0}\pmod{z^{2k}}\)。
有标号有根树复合任意生成函数
求\(F=G(H)\)，其中\(G\)是有标号有根树的EGF，也就是\(G(z)=1+\sum_{i=1}^{\infty}\frac{i^{i-1}}{i!}z^i\)。
考虑有标号有根树的EGF是\(G=z\exp G\)，它的含义是显然的。
然后我们把这个东西代回去，得到\(G(H)=He^{G(H)}\)。根据牛迭构造\(f(F)=F-He^F\)，然后\(f(F_0)\)好说，\(f^{\prime}(F_0)=1-He^F\)，算即可。
这指出，GF的性质由它满足的方程给出，而它的系数在处理的过程中并不是那么有用(但是当然作为结果很有用)。
烷基计数
解方程\(F(z)=z\frac{F(z)^3+3F(z^2)F(z)+2F(z^3)}{6}+1\)。
我们当然可以分治FFT做这个东西，不过这个式子看起来非常麻烦不是很好做。我们考虑牛顿迭代。
设\(f(F(z))=F(z)-(z\frac{F(z)^3+3F(z^2)F(z)+2F(z^3)}{6}+1)\)，那么\(f(F)\)很好办；而\(f^{\prime}(F)\)，由于有复合，似乎不是很好办啊?
实际上，\(F(z^2) mod z^n\)的结果只跟\(F\)的前\(\lfloor n/2\rfloor\)项有关，而\(F\)的这些项跟\(F_0\)的这些项是相同的。所以求导的时候，\(F_0\pmod{z^k}\)是常多项式，\(F(z^2)\pmod{z^{2k}},F(z^3)\pmod{z^{2k}}\)这些也是常多项式，另外对\(F(z)\)求导时\(z\)也是个常多项式。于是容易得到\(f^{\prime}(F(z))=1-z\frac{3F(z)+3F(z^2)}{6}\)，迭代即可。
无标号有根树计数
解方程\(F(z)=z\mathcal{E}(F(z))=z\exp\sum_{i=1}^{\infty}\frac{F(z^i)}{i}\)。
跟奇怪的东西2类似，我们发现如果\(F(z)\pmod{z^k}\)已经确定，那么\(i\geq 2\)时，\(F(z^i)\pmod{z^{2k}}\)是常多项式。我们设\(T(z)=\sum_{i=2}^{\infty}\frac{F(z^i)}{i}\pmod{z^{2k}}\)，那么就可以构造\(f(F)=\ln F-T-F\)。
现在很容易算出\(f^{\prime}(F)=\frac{1}{F}-F\)，但是对于\(f(F)\)，我们应该怎么计算\(T\)呢?考虑在迭代过程中维护，每一位计算出来之后我们直接爆力贡献到所有倍数，容易发现这样的复杂度是调和数的\(O(n\log n)\)，于是总复杂度还是\(O(n\log n)\)。