生成函数浅谈
羊驼说，要当老师，所以强大的羊驼教会了我们生成函数。
羊驼说，我们有卷积，所以生成函数的问题通常可以在带 \(log\) 的时间复杂度内解决这类问题。
普通型生成函数
数列 \(1,1,1,1,1,1\) 的普通型生成函数就是 \(1+x+x^2+x^3+x^4+x^5\)。
而数列 \(1,1,\cdots,1,1,\cdots\) 的普通型生成函数就是 \(1+x+x^2+x^2+\cdots +x^n+\cdots\)。
羊驼说，写成展开形式形式太麻烦，所以羊驼教会了我们封闭形式。
设 \(F(x)=1+x+x^2+x^3+x^4+x^5\)
则 \(xF(x)=x+x^2+x^3+x^4+x^5\)
所以 \(F(x)=\frac{1-x^6}{1-x}\)
对于无穷数列也是同理，我们可以假定它收敛，得到封闭形式。
设 \(F(x)=1+x+x^2+\cdots\)
则 \(xF(x)=x+x^2+x^3+\cdots\)
所以 \(F(x)=\frac{1}{1-x}\)
下面是一些常用的无穷数列普通型生成函数的封闭形式和展开形式的对应关系：
\(a_i=p^i x^i,F(x)=\frac{1}{1-px}\)
\(a_i=x^{pi},F(x)=\frac{1}{1-x^p}\)
\(a_i=(i+1)x^i,F(x)=\frac{1}{(1-x)^2}\)
\(a_i=\binom m i x^i,F(x)=(1+x)^m\)（二项式定理）
指数型生成函数
羊驼说，她不会组合数，所以就有了指数型生成函数。
\(1,1,\cdots\) 的指数型生成函数就是 \(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\)
指数型生成函数通常用来消掉组合数中的阶乘，并且一般是无穷数列。
对于指数型生成函数的封闭形式和展开形式来说，二者对应关系如下：
因此，指数型生成函数的封闭形式通常是 \(e\) 的幂次。
下面是一些常用的无穷数列指数型生成函数的封闭形式和展开形式的对应关系：
\(a_i=\frac{x^i}{i!},F(x)=e^x\)
\(a_i=(-1)^i\frac{x^i}{i!},F(x)=e^{-x}\)
\(a_i=\frac{x^{2i}}{2i!},F(x)=\frac{e^x+e^{-x}}{2}\)
\(a_i=\frac{x^{2i+1}}{(2i+1)!},F(x)=\frac{e^x-e^{-x}}{2}\)
于是我们就学会了生成函数。
例题
羊驼说，要有例题，所以我们来到了 P2000 拯救世界。
两位大神的召唤方法显然都可以写成收封闭形式，只要约一下分，就可以得到最终的封闭形式。
\(kkksc03\)：
金：\(F(x)=\frac{1}{1-x^6}\)
木：\(F(x)=\frac{1-x^{10}}{1-x}\)
水：\(F(x)=\frac{1-x^6}{1-x}\)
火：\(F(x)=\frac{1}{1-x^4}\)
土：\(F(x)=\frac{1-x^8}{1-x}\)
\(lzn\)：
金：\(F(x)=\frac{1}{1-x^2}\)
木：\(F(x)=\frac{1-x^2}{1-x}\)
水：\(F(x)=\frac{1}{1-x^8}\)
火：\(F(x)=\frac{1}{1-x^{10}}\)
土：\(F(x)=\frac{1-x^4}{1-x}\)
乘起来可得:
再转换回展开形式：
答案即为 \(\binom {n+4} 4\)。
可以用 \(NTT\) 加速高精度。
羊驼说，这种板子题太简单，所以就有了 P4841 城市规划
我们枚举 \(1\) 节点所在的连通块大小，设 \(f(x)\) 是合法连通图数量，\(g(x)\) 是合法图数量，则可得 \(g(n)=\sum_{i=1}^n \binom {n-1} {i-1} f(i)g(n-i)\)
同时我们已知 \(g(n)=2^{\binom n 2}\)，开始推柿子。
\(\begin{alignedat}{2}2^{\binom n 2}&=\sum_{i=1}^n \binom {n-1} {i-1} f(i)2^{\binom {n-i} 2}\\ \frac{2^{\binom n 2}}{(n-1)!}&=\sum_{i=1}^n \frac{f(i)}{(i-1)!}\frac{2^{\binom {n-i} 2}}{(n-i)!} \end{alignedat}\)
多项式求逆即可。