生成函数做题做题记录
生成函数记录。
1 烷基计数
无标号，有根树的计数问题。
当年手推容斥不burnside可牛逼死了。。。。
大概设 \(F(x)\) 为生成函数，由于有根只需要把儿子卷起来即可。
\(F^3(x)\) 会算重， \({1,2,3}\Longleftrightarrow2,1,3\cdots\),考虑本质上是 \(3\) 阶置换群作用在 \(F(x)\) 上。
根据burnside引理。
\(F(x)=\frac{1}{|G|}(\begin{bmatrix}3\\1\end{bmatrix}F(x^3)+\begin{bmatrix}3\\2\end{bmatrix}F(x^2)F(x)+\begin{bmatrix}3\\3\end{bmatrix}F^3(x))\)
牛顿迭代。
需要注意的是 \(F=F_0-\frac{G(F_0)}{G'(F_0)}\bmod x^n,l=\lceil\frac{n}{2}\rceil\)。
注意分子必须是恰好 \(\bmod x^n\),然后他的 \(0,1,\cdots,l-1\) 都是 0，所以分母只需要 \(\bmod n-l\) 求逆即可。
2烷烃计数
如果我们主观上给烷烃定根，那么他可以看成一个由四个烷基拼成的结构。
我们该如何定根？
树哈希的经历告诉我们重心往往有着更好的性质。
如此，对于无根树我们有了以下两种方法：
1最大子树小于 \(n\) 的一半
如果 \(n\) 是奇数那么一定只有一个重心。我们钦定在重心处计数，换句话说就是让根的四颗子树大小都 \(\leq n/2\)。
这样我们只是在‘烷基计数’的基础上在最后合并，这回变成了 \(4\) 阶群作用在 \(F(x)\) 上。
类似的使用 burnside，不难得出： \[ F(x)=\frac{1}{|G|}(6F(x^4)+3F^2(x^2)+9F(x^3)F(x)+6F^2(x)F(x^2)+F^4(x)) \] 对于 \(n\) 是偶数，根据计数方式，会多或者少算一些情况。
我不让 \(n/2\) 被算入，所以会少算，少算了存在 \(n/2\) 的。
可以看作两个大小为 \(n/2\) 的烷基拼起来。
组合数算算就好了。
2容斥
我们计算每个点为根的情况；减去每条边分割出两个子树的情况；加上存在两个重心，并且重心的子树同构的情况。
在有标号egf计数的时候，考虑尽管我们分配了标号，但是在标号所“依附”的计数对象重排时，会带来 \(\frac{1}{k!}\) 的重复计数。
当然也是这些使得在有标号计数时 \(e^x\) 是多么重要。
拉格朗日反演
拉反：条件是若 \(F,G\) 两个多项式常数项是 \(0\)，一次方项不是 \(0\)，并且复合结果是 \(G(F(x))=x\)，推出 \[ [x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n \] 证明：
首先 \(G(x)=\sum a_ix^i\)，那么： \[ \begin{aligned} G(F(x))=\sum a_iF^i(x)&=x\\ \text{d}\sum a_iF^i(x)&=\text{d}x\\ \sum_{i\ge 1} a_i\times i\times F^{i-1}(x)F'(x)&=1\\ F^{-n}(x)\sum_{i\ge 1} a_i\times i\times F^{i-1}(x)F'(x)&=1\cdot F^{-n}(x)\\ \end{aligned} \] 此时提取 \([x^{-1}]\) 项，考虑 \(lhs\) 会有很多项被舍弃无视。 \[ \sum_{i\ge 1} a_i\times i(F^{i-1-n}(x)F'(x)) \] 观察括号里这一项，当 \(i\neq n\) 时，等于 \(\frac{1}{i-n}(F^{i-n}(x))'\)
当 \(i\ge n\) 时显然没有 \([x^{-1}]\) 项。
当 \(i<n\) 时，考虑 \(\frac{1}{F^{n-i}(x)}\) 在求导后一定不能有 \(\frac{1}{x}\) 项，考虑大概只有 \(\ln\) 求导能得到 \(\frac{1}{x}\)，这显然不符合 \(F(x)\) 形式。
所以 \(lhs\) 只剩下了 \(a_n\times n \times F^{-1}(x)F'(x)\)。 \[ \begin{aligned} [x^{-1}]a_n\times n\times F^{-1}(x)F'(x)&=[x^{-1}]F^{-n}(x)\\ F^{-1}(x)F'(x)&=\frac{a_1+2\times a_2x+3\times a_3x^2+\cdots}{a_1x+a_2x^2+a_3x^3+\cdots}\\ \\ F^{-1}(x)F'(x)&=\frac{1}{x}\cdot \frac{a_1+2\times a_2x+3\times a_3x^2+\cdots}{a_1+a_2x^1+a_3x^2+\cdots} \end{aligned} \] 考虑后面那个式子由于可逆并且仅有的 \(x^0\) 次项也是 \(1\) 不难发现 \([x^{-1}]=1\)。
综上： \[ a_n\times n=[x^{-1}]F^{-n}(x) \] 换种写法也就是: \[ \begin{aligned} [x^n]G(x)=\frac{1}{n}[x^{-1}]\frac{1}{(F^n(x))}\\ [x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n\\ \end{aligned} \]
大朋友与多叉树。
<<<<<<< Updated upstream 考虑限制儿子个数相当于构造了 \(G(x)=\sum\)
记录一下多点求值和一道模拟赛题吧！
感觉范德蒙德矩阵我根本没有学明白（（（（（（（（，现在先咕咕咕，有时间在gao。 \[ \begin{bmatrix} &1,&x_1,&\cdots,&x_1^{n}\\ &1,&x_2,&\cdots,&x_2^{n}\\ &\vdots&\vdots&\ddots&\vdots\\ &1,&x_{n}^{}&\cdots &x_{n}^{n} \end{bmatrix}\vec{a}=\vec{y} \] 那么多线求值是想快速的求矩阵乘法。
这个有一种非常神仙的叫做转置定理，大概说的就是如果一系列的线性变换能快速的求解，那么这一系列的变换的转置变换也能快速求解。
我们发现了对于 \(M^{T}\) 的乘法有一定的性质，即： \[ \begin{bmatrix} &1,&1,&\cdots,&1\\ &x_1,&x_2,&\cdots,&x_{n}\\ &\vdots&\vdots&\ddots&\vdots\\ &x_1^{n},&x_{2}^{n}&\cdots &x_{n}^{n} \end{bmatrix}\vec{a}=\vec{y} \] 写成生成函数形式 \[ \sum y_i\lambda^i=\sum_{i}\sum_{j}x_j^ia_j\lambda^i=\sum_{j}a_j\sum_{i}x_j^i\lambda^i=\sum_{j}a_j\frac{1}{1-x_j\lambda} \] 对这个东西求解可以使用经典的维护 \(\frac{L_a(x)}{L_b(x)},\frac{R_a(x)}{R_b(x)}\) 加法后合并成 \(\frac{L_aR_b(x)+L_b(x)R_a(x)}{L_b(x)R_b(x)}\)。
这样我们有分治的 \(n\log^2n\) 的做法了。
在转置意义下，我们的加法卷积变成了减法卷积。（（转置定理这块咕咕咕了
这样不难发现 + 卷积，变成了 - 卷积。
即 \(F\ominus G(x)=\sum_{k}(\sum\limits_{a-b=k}f_a\times f_b )x^k\)。
这样我们从 \(\ominus\) 考虑这个问题便有了合适的理由了。
\(F(a_i)=[x^0]F\ominus\frac{1}{1-a_ix}\)，求值看作一行 \(\oplus\) 卷积，那么转置意义下就是一列，也就是 \(\ominus\) 卷积。
另有 \(F\ominus (G\times H)=(F\ominus G)\ominus H\)。考虑 \(A^T\times B^T=(A\times B)^T\)。
那么类似的考虑分治求解： \[ G_{l,r}(x)=F\ominus(\prod_{i=l}^r \frac{1}{1-a_ix}) \] 从上向下分治 \(G_{l,mid}=G_{l,r}\ominus\prod_{i=mid+1}^r 1-a_ix\)
接下来我们并未完全完成，因为精度呢？
对于一次 \([x^0]F\ominus \frac{1}{1-ax}\) 精度显然只需要 \(\bmod x^1\)。
那么一个 \(G_{l,r}\) 精度只需要 \(\bmod x^{r-l+1}\)，归纳法证明，\(G_{l,mid}\) 精度需要 \(\bmod x^{mid-l+1}\)
而 \(\prod_{i=mid+1}^r 1-a_ix\) 精度是 \(x^{r-mid}\), 所以最后 \(G_{l,r}\) 需要的是 \(\bmod x^{r-mid+mid-l+1} =\ \bmod x^{r-l+1}\)
所以此时才完事，根据主定理（咕咕咕我不会）复杂度 \(O(n\log ^2n)\)。
至于模拟赛那道题。。。。。就是对范德蒙德矩阵的转置求逆。。。。。。。。
大概写出生成函数
考虑限制儿子个数相当于构造了 \(G(x)=\sum_{i\in D}x^i\)。
所以有复合方程 \(G(F(x))=F(x)+x\)，加的 \(x\) 是单独成树的叶子。
让 \(G'(x)=G(x)-x\)，所以方程 \(G'(F(x))=x\),\(G'(x),F(x)\) 互为复合逆，直接拉反求 \(F(x)\) 一项即可。
考虑为什么能拉反 \([x^0]G'(x)=0\) 组合意义不能算叶子，或者说叶子系数是常量 \(0\)。
\([x^1]G'(x)\neq0\) 这个实在说不能一直填非叶子节点的中间节点，否则这个是发散的。
Link
问1类斯特林数。
\(n\gets n+1\)。
\([x^t]x^{\overline{n}}\bmod p\)。 \[ \begin{aligned} n&=pa+b\\ x^{\overline{n}}&=(x^{\overline{p}})^a\times x^\overline{b}\\ x^{\overline p}&=x^p-1 \bmod p\\ x^{\overline{n}}&=(x^p-1)^a\times x^\overline{b}\\ \end{aligned} \] 此时我们应该考虑如何计数了。
如果此时 \(F(x)\) 表示 \(f(i)=\sum_{x\in S} [x\bmod p=i]\) 的生成函数。
我们惊喜地发现前后独立了。
因为前面最近的两项距离是 \(p\)，而后面的次数 \(b<p\)。
似乎可以模意义乘法卷积。
前面的呢？
把 \(a\) 拆成 \(p\) 进制的 \(A_i\)。
又是一堆次方相互独立。
Pre 一道 经典题。
这个题的结论是对于每个连通块大小是 \(c_i\) 的连成是树的方案数是： \[ n^{k-2}\prod c_i \] 证明通过prufer 序列描述，注意和 prufer 序列关系最紧密的是度数！！！！而不是最后剩下什么这种东西！！！！！
那么我们枚举每个连通块出现次数，答案就是： \[ \begin{aligned} &\sum_{d_i}\binom{k-2}{d_i-1}\prod c_i^{d_i}\\ &=(k-2)!\sum_{d_i}\prod \frac{c_i^{d_i}}{(d_i-1)!}\\ &=(k-2)![x^{k-2}]\prod\int e^{c_ix}\\ &=(k-2)![x^{k-2}]\prod c_ie^{\sum c_ix}=n^{k-2}\prod c_i \end{aligned} \]
那么如何对边双计数呢？首先肯定是得容斥，就是说我们钦定随意选若干个连通块，然后给这些连通块里面连边，这样就好。
正确性还是因为本质上会多算 \((-1)^i\binom{n}{i}\) 次，就好了。
然后我们可以枚举钦定的连通块数，我们相当于进行“集合无序”的划分，所以贡献是 \(\frac{F^k(x)}{k!}\) （除掉的是经典的集合序）。然后我们可以把分集合和连边想成两部分，这两部分肯定不交，所以先把集合划分出来乘上，给集合连边的就好。
最后写出来大体是： \[ (\frac{-1}{n^2})\sum_{k} \frac{(F_1(x))^k}{k!},[x^k]F_1=[x^k]F\times(-n)\times (k) \] 大概 \(F_1\) 是吧容斥系数放进去了，枚举 \(k\) 这个可以直接EXP。
时刻要记得可以将 EGF 乘法理解成染色。