「总结」多项式生成函数相关（3）

今天是生成函数了。
。。。
是我学的最难的多项式部分了。
其实我也可以说是现学现卖，学的不好讲的不好大家见谅。
我之前讲的大部分东西都可以和生成函数相结合。
生成函数分成三种。
我们一个一个来。

1.普通型生成函数（(OGF)）
对于一个已知的数列({a_i})。
其(OGF)为：

[F(x)=sumlimits_{i=0}^{infty}a_ix^i ]

例如：({1})的(OGF)就是：

[F(x)=sumlimits_{i=0}^{infty}x^i=frac{1}{1-x} ]

很多时候我们用生成函数的原因是，我们可以把一个数列转化成一个简单的形式。
例如(frac{1}{1-x})
如果我们让两个(OGF)相乘会怎么样呢？
简单的例子：
比如说如果我们可以选两个物品，分别从两组中选择。
第一组物品的体积和每种体积的物品种类用数列({a_i})来表示。
第二组物品的体积和每种体积的物品种类用数列({b_i})来表示。
设({a_i})的(OGF)为(A(x)),({b_i})的(OGF)为(B(x))
那么((A(x)B(x))_i)就是选择的两个物品的体积和为(i)的方案数。
(OGF)经常来解决这种组合问题。

例：http://hzoj.com/contest/126/problem/5
裸的容斥题，我们将数列换成生成函数。
设一个的(OGF)为(A(x))
两个合在一起的为(B(x))
三个合在一起的为(C(x))
那么答案就是：

[frac{A^3(x)-3A(x)B(x)+2C(x)}{6}+frac{A^2(x)-B(x)}{2}+A(x) ]

做四次(DFT)即可。

例：http://hzoj.com/problem/917
也挺裸的。
我们考虑求前缀和的过程是怎么样的。
对于一个数列({a_i})，设其前缀和为({b_i})
那么:

[{b_i}={a_i}*{1}=sumlimits_{j=0}^{i}a_j ]

这个时候可以用多项式快速幂来搞了。
但是常数过大，(ln+exp)
这个题时限开到了(200ms)过不掉。
考虑如何优化。
我们设(A(x))为({1})的(OGF)。
那么：

[A(x)=sumlimits_{i=0}^{n}x^i ]

考虑一下这个(OGF)自乘(k)次后第(i)项的系数是什么含义。
事实上是取(k)个自然数，加和之后为(i)的方案。
这样直接用挡板解决就可以了。
这个系数就是：

[inom{i+k-1}{k-1} ]

那么也就是说：

[A^k(x)=sumlimits_{i=0}^{n}inom{k+i-1}{k-1}x^i ]

这样就只需要三次(NTT)了。

2.指数型生成函数((EGF))
对于一个数列({a_i})
其(EGF)为：

[F(x)=sumlimits_{i=0}^{infty}frac{a_i}{i!}x^i ]

比如(1)的(EGF)为：

[F(x)=sumlimits_{i=0}^{infty}frac{x^i}{i!}=e^x ]

同样是一个级数求和。
相比之下(EGF)用来解决排列问题。
比如说这样一个问题：
从(A)中拿出任意多个相同物品，从(B)中拿出任意多个相同物品，如果认为拿出来的物品的顺序不同视为不同方案，求拿出的物品个数为(i)的方案数。
设(EGF)为：$$G(x)=sumlimits_{i=0}^{infty}frac{x^i}{i!}$$
设答案数组的(EGF)为：$$R(x)=sumlimits_{i=0}^{infty}frac{res_i}{i!}x^i$$
那么:

[R(x)=G^2(x) ]

这里就没有(OGF)那么显然了。
考虑一下为什么。
对于一个可重集合(S),设(left|S ight|=n),设其中每种物品的个数为(a_i)。
那么这个集合的可重排列的方案就是：

[frac{n!}{prodlimits_{i=1}^{w}a_i!} ]

这样我们再来观察这个卷积的过程。
相当于是把相同的物品的系数乘了一个(frac{1}{i!})
而最后的系数的和下面除了一个(i!)，相当于可重集合上面乘的(n!)。

大概，可以懂吧？

例：http://hzoj.com/contest/126/problem/10
在大神们都用分治发发塔(AC)之后，我们再次看一下这道题能否有低于(nlog^2n)的复杂度。
设(n)个点无向图的个数为(g(n)=2^{inom{n}{2}}),设(n)个点联通图的个数为(f(n))。
列出式子：

[g(n)=sumlimits_{i=1}^{n}inom{n-1}{i-1}f(i)g(n-i) ]

拆一下：

[g(n)=sumlimits_{i=1}^{n}frac{(n-1)!}{(i-1)!(n-i)!}f(i)g(n-i) ]

[frac{g(n)}{(n-1)!}=sumlimits_{i=1}^{n}frac{f(i)}{(i-1)!}frac{g(n-i)}{(n-i)!} ]

设(G_0(x)=sumlimits_{i=0}^{n}frac{g(i+1)}{i!}x^i),(G_1(x)=sumlimits_{i=0}^{n}frac{g(i)}{i!}x^i),(F(x)=sumlimits_{i=0}^{n}frac{f(i+1)}{i!}x^i)
这样的话：

[G_0(x)=F(x)G_1(x) ]

[F(x)=frac{G_0(x)}{G_1(x)} ]

也就是一个多项式求逆了。

3.概率生成函数（咕咕咕我不会暂时不想学）(Upd:)已经学了。
我们设一个离散型随机变量(X)的概率生成函数为：

[F(x)=sumlimits_{i=0}^{infty}P(X=i)x^i ]

那么：

[F'(x)=sumlimits_{i=0}^{infty}iP(X=i)x^i ]

也就是说：

[F'(1)=sumlimits_{i=0}^{infty}iP(X=i)=E(X) ]

这样我们不断的求导下去可以得到：

[F^{(k)}(1)=sumlimits_{i=0}^{infty}i^{underline{k}}P(X=i)=E(X^{underline{k}}) ]

这样也给除了一种便捷的求方差的方式：

[egin{aligned} Var(X)&=E((X-E(X))^2)\ &=E(X^2-2XE(X)+E^2(X))\ &=E(X^2)-2E(X)E(X)+E^2(X)\ &=E(X^2)-E^2(X)\ &=E(X(X-1))+E(X)-E^2(X)\ &=F''(1)+F'(1)-(F'(1))^2\ end{aligned}]

4.应用
先来几个(EGF)的。

fr.一个含有(n)个点的树，如果令度数最大的点的度数为(m),求方案数。

(prufer)序列。
转化为长度为(n-2)的序列中，([1,n])中的数出现次数最多的为(m-1)次的方案数。
继续转化为，出现最大的为(m-1)减去出现最大的为(m-2)的。
构造生成函数：

[F(x)=sumlimits_{i=0}^{m-1}frac{x^i}{i!} ]

那么：

[ans=[x^{n-2}]F^n(n) ]

se:http://hzoj.com/contest/126/problem/10
城市规划。还是这个题。
在各位大神甚至用生成函数和多项式求逆(AC)这道题之后我还想告诉你：

[我没有脑子都可以切这题。 ]

我们现在用(EGF)来搞一个更加无脑的做法。
我们设(f(n))为(n)个点有标号无向联通图的个数，(g(n)=2^{inom{n}{2}})为(n)个点有标号无向图。
设(f(n))的(EGF)为：

[F(x)=sumlimits_{i=0}^{infty}frac{f(i)x^i}{i!} ]

[G(x)=sumlimits_{i=0}^{infty}frac{g(i)x^i}{i!} ]

我们枚举一个无向图有几个联通块。
得到如下的式子：

[G(x)=sumlimits_{i=0}^{infty}frac{F^i(x)}{i!}=e^{F(x)} ]

那么：

[F(x)=ln(G(x)) ]

直接多项式(ln)即可。

来几个背包问题：
fr.体积为(i)的物品有(a_i)种，每种无限个，求([0,n])所有容积的方案。
设体积为(i)的物品的(OGF)为(F(x))
那么由于有无限个。
首先复习两个级数求和公式：

[sumlimits_{i=0}^{infty}x^j=frac{1}{1-x} ]

[sumlimits_{i=1}^{infty}frac{x^j}{j}=-ln(1-x) ]

所以：

[F(x)=sumlimits_{i=0}^{infty}(x^i)^j ]

设答案数组的(OGF)为(A(x))
那么：

[egin{aligned}\ A(x)&=prodlimits_{i=1}^{n}F_i^{a_i}(x)\ &=prodlimits_{i=1}^{n}(sumlimits_{i=0}^{infty}(x^i)^j)^{a_i}\ &=prodlimits_{i=1}^{n}(frac{1}{1-x^i})^{a_i}\ &=exp(ln(prodlimits_{i=1}^{n}(frac{1}{1-x^i})^{a_i}))\ &=exp(sumlimits_{i=1}^{n}a_i(0-ln(1-x^i)))\ &=exp(sumlimits_{i=1}^{n}a_i(-ln(1-x^i)))\ &=exp(sumlimits_{i=1}^{n}a_isumlimits_{j=1}^{infty}frac{(x^i)^j}{j})\ &=exp(sumlimits_{j=1}^{infty}frac{1}{j}sumlimits_{i=1}^{n}a_i(x^j)^i)\ &=exp(sumlimits_{j=1}^{infty}frac{1}{j}A(x^j))\ end{aligned}]

也就是说对于第(j)项，只需要累加(j)的倍数项。
那么复杂度是：

[sumlimits_{i=1}^{n}frac{n}{i}=nsumlimits_{i=1}^{n}frac{1}{i}=nH_n=nln(n) ]

se.体积为(i)的物品有(a_i)种，每种有一个，求([0,n])所有容积的方案。
设体积为(i)的物品的(OGF)为(F_i(x))
那么：

[F_i(x)=1+x^i ]

设答案数组的(OGF)为(A(x))。
那么:

[egin{aligned}\ A(x)&=prodlimits_{i=1}^{n}F_i^{a_i}(x)\ &=prodlimits_{i=1}^{n}(1+x^i)^{a_i}\ &=exp(ln(prodlimits_{i=1}^{n}(1+x^i)^{a_i}))\ &=exp(sumlimits_{i=1}^{n}a_iln(1+x^i))\ &=exp(sumlimits_{i=1}^{n}a_isumlimits_{j=1}^{infty}frac{(-1)^{j-1}(x^i)^j}{j})\ &=exp(sumlimits_{j=1}^{infty}frac{(-1)^{j-1}}{j}sumlimits_{i=1}^{n}a_i(x^j)^i)\ &=exp(sumlimits_{j=1}^{infty}frac{(-1)^{j-1}}{j}A(x^j))\ end{aligned}]

一样是调和级数的复杂度。