生成函数做题笔记
-
生成函数的入门题，对于每一个限制条件，若为 (k) 的倍数则生成函数为 (frac{1}{1-x^{k}})，若为 (ge k) 则为 (frac{1-x^{k+1}}{1-x})。最后用广义二项式定理求出第 (n) 项系数即可。
-
CF438E The Child and Binary Tree
设 (f_i) 表示权值和为 (i) 的方案数，记 (a_i) 为权值 (i) 的出现次数，则：
[f_i= egin{cases} 1&i=0 \ sum_{j+p+q=i}{a_jf_pf_q}&ige1 end{cases} ]记 (A(x)=sum_{i=1}^{m}{a_ix^i})，(f_i) 的 (OGF) 为 (F(x))，则 (F(x)=1+A(x)F^2(x))。（ (+1) 是补全 (f_p,f_q) 的常数项）
再一些题解中，直接使用求根公式来解出上面的式子，但是考虑 (a_i) 的定义，发现 (A(x)) 的零次项为 (0)，故不存在逆元，所以不能直接求根。可以先将等式两边同乘 (A(x))，整理可得：
[A^2(x)F^2(x)-A(x)F(x)+A(x)=0 \ (A(x)F(x)-frac{1}{2})^2=frac{1}{4}-A(x) ]若 (A(x)F(x)-frac{1}{2}=sqrt{frac{1}{4}-A(x)})（ (frac{1}{4}-A(x)) 的零次项为 (frac{1}{4})，存在逆元），那么：(A(x)F(x)=frac{sqrt{1-4A(x)}+1}{2})。但是，右式是零次项为 (1)，但是左边的零次项为 (0)，所以舍去。
所以 (A(x)F(x)-frac{1}{2}=-sqrt{frac{1}{4}-A(x)})，化简以后得到：
[F(x)=frac{2}{1+sqrt{1-4A(x)}} ]多项式开根求逆即可。
-
多项式优化完全背包
设物品体积为 (v) ，那么该物品的生成函数为 (sum_{ige 0}{[i\%v=0]x_i})，也就是 (frac{1}{1-x^{v}})。
答案就是 (m) 个生成函数的卷积。但是这样的复杂度还不如DP，所以需要优化。
考虑将乘法化为加法。一种常见的方法是求 (ln) 再 (exp)。
由 (ln(1-A(x))=-sum_{ige1}{frac{A_i(x)}{i}})可得：
[ln(1-x^v）=-sum_{ige1}{frac{x^{vi}}{i}} ]我们只需要枚举 (v imes i)，根据调和级数，复杂度是 (O(mln m))。
枚举每一种物品，分别加到对应的系数中，就完成了取 (ln) 和求和的操作，然后求 (exp) 再求逆即可。
-
这题有一个比较巧妙（省事）的做法。
设多项式 (f_i) 表示 (i) 个点的无向连通图个数 (/i!) ，则答案为 (f_n imes n!)。
设多项式 (g_i) 表示 (i) 个点的无向图个数 (/i!)，不难发现 (g_i=frac{2^{nchoose 2}}{i!})。
再考虑 (g) 和 (f) 的关系，因为一个无向图可以看作是由若干个无向连通图拼在一起的，所以我们枚举连通块的数量：
[g=sum_{k=0}^{infty}{frac{f^k}{k!}} ]为什么要除以 (k!) 呢，因为我们再计算 (f) 与 (g) 时通过除以阶乘消除了标号的影响，而 (f_k) 所乘的 (k) 个元素是有先后顺序的，所以要除以全排列来消除标号。
通过观察，上面的式子可以化为：
[g=e^f ]即：
[f=ln g ]这个转化在 (cgz) 的课件上可以找到。
-
首先，斐波那契数列 (f(x)) 的生成函数为：
[F(x)=frac{x}{1-x-x^2} ]令答案为 (g(n))，考虑枚举最后一个数字，在原来的基础上乘以该数的斐波那契值，即：
[g(n)= egin{cases} sum_{i=0}^{n}{f(i)*g(n-i)} &(n eq0) \ 1 &(n=0) end{cases} ]设其生成函数为 (G(x))，则有：
[G=G*F+1 \G=frac{1-x-x^2}{1-2x-x^2} \G=1+frac{x}{1-2x-x^2} ]只需要展开 (-frac{x}{x^2+2x-1}) 即可。
我们知道 (frac{1}{1-A(X)}=sum_{ige0}{A^i(x)x^i})，所以我们想把式子往这上面靠。
先解出 (x^2+2x-1=0) 的两根 (x_1,x_2)，那么：
[egin{split} -frac{x}{x^2+2x-1}&=-frac{x}{(x-x_1)(x-x_2)} \&=frac{x}{x_2-x_1}(frac{1}{x-x_1}-frac{1}{x-x_2}) \&=frac{x}{x_2-x_1}(frac{1}{x_2} imesfrac{1}{1-x/x_2}- frac{1}{x_1} imes frac{1}{1-x/x_1}) \&=frac{1}{x_2-x_1}(sum_{i=0}{frac{x^{i+1}}{x_2^{i+1}}}-sum_{i=0}frac{x^{i+1}}{x_1^{i+1}}) end{split} ]所以第 (n) 项的系数 (g(n)=frac{1}{x_2-x_1} imes(frac{1}{x_2^n}-frac{1}{x_1^n}))。
带入得到：(g(n)=frac{sqrt{2}}{4}[(1+sqrt{2})^n-(1-sqrt2)^n])。
至于如何求 (sqrt2) 在模 (1e9+7) 下的值，要用到二次剩余，具体可以看 这篇博客，这里给出参考值：(59713600)。
由于 (n) 很大，需要用到扩展欧拉定理，在读入时对 (P-1) 即 (1e9+6) 取模。
-
要用到 二项式反演 相关知识。
设 (G(k)) 表示恰好 (k) 中颜色出现了 (S) 次的方案数。
对于这一类问题，我们可以考虑钦定 (k) 种颜色，每种强行染色 (S) 次，剩下的随便染，即：
[{m choose k}*frac{n!}{(S!)^k(n-S imes k)!}*(m-k)^{n-S imes k} ]但是这个东西并不是 (G)，因为这会重复计数。比如，当我们钦定 (a,b) 两种颜色的时候，可能还有一种颜色 (c) 也正好出现了 (S) 次（因为剩下的是随便选的）。因此，我们令上式为 (F(k))，考虑 (F) 与 (G) 的关系。
我们发现，当 (F) 取 (k)，(G) 取 (i) 时，恰好有 ({i choose k}) 种情况 (G) 会对 (F) 造成贡献，所以可以得到：
[F(k)=sum_{i=k}^{n}{{i choose k}G(i)} ]已知 (F) 求 (G)，于是套用二项式反演得到：
[G(k)=sum_{i=k}^{n}{(-1)^{i-k}{i choose k}F(i)} ]拆开组合数：
[G(k)=sum_{i=k}^{n}{(-1)^{i-k}frac{i!}{k!(i-k)!}F(i)} \G(k)=frac{1}{k!}sum_{i=k}^{n}{frac{(-1)^{i-k}}{(i-k)!}i!F(i)} ]把 (F) 翻转一下就可以卷积了！
实现起来细节还是蛮多的……