生成函数中某些计数问题

一些生成函数的计数问题的做法

背包计数

$1:\mathrm{有}{\sum }_{1\le i\le n}ai\mathrm{种}\mathrm{物}\mathrm{品}，\mathrm{体}\mathrm{积}\mathrm{为}i\mathrm{的}\mathrm{物}\mathrm{品}\mathrm{有}{a}_i\mathrm{种}。\mathrm{每}\mathrm{种}\mathrm{物}\mathrm{品}\mathrm{有}\mathrm{无}\mathrm{限}\mathrm{个}，\mathrm{求}\mathrm{每}\mathrm{种}\mathrm{体}\mathrm{积}\mathrm{的}\mathrm{方}\mathrm{案}\mathrm{数}$

$$\prod _{i=1}^n(\sum _{j=0}^{\mathrm{\infty }}{x}^{ij}{)}^{a_i}=\exp (\sum _{i=1}^n{a}_i\ln (\frac{1}{1-x^i}))$$

至于$\ln (\frac{1}{1-x^i})$可以变成$-\ln (1-x^i)$然后泰勒展开
或者用$f=\ln (g)\to g=\int \frac{f^{\prime }}{f}=\int \frac{\sum _{j=1}^{\mathrm{\infty }}ij{x}^{ij-1}}{\frac{1}{1-x^i}}$搞

得到

$$\exp (\sum _{i=1}^n{a}_i\sum _{j=1}^{\mathrm{\infty }}\frac{x^{ij}}{j}))$$

调和级数处理再$\exp$
复杂度$O(nlogn)$

$2:\mathrm{有}{\sum }_{1\le i\le n}ai\mathrm{种}\mathrm{物}\mathrm{品}，\mathrm{体}\mathrm{积}\mathrm{为}i\mathrm{的}\mathrm{物}\mathrm{品}\mathrm{有}{a}_i\mathrm{种}。\mathrm{每}\mathrm{种}\mathrm{物}\mathrm{品}\mathrm{只}\mathrm{有}1\mathrm{个}，\mathrm{求}\mathrm{每}\mathrm{种}\mathrm{体}\mathrm{积}\mathrm{的}\mathrm{方}\mathrm{案}\mathrm{数}$

类似的生成函数为

$$\prod _{i=1}^n(1+x^i{)}^{a_i}$$

后面的没区别

$3:$
$\mathrm{有}n\mathrm{种}\mathrm{物}\mathrm{品}，\mathrm{第}i\mathrm{种}\mathrm{物}\mathrm{品}\mathrm{的}\mathrm{体}\mathrm{积}\mathrm{为}i。\mathrm{第}i\mathrm{中}\mathrm{物}\mathrm{品}\mathrm{有}ai\mathrm{个}$

类似生成函数为

$$\prod _{i=1}^n(\frac{1-x^{(a_i+1)i}}{1-x^i})$$$$=\exp (\sum _{i=1}^n\ln (1-x^{(a_i+1)i})-\sum _{i=1}^n\ln (1-x^i))$$

两部分也没区别

树的计数

$$\begin{gathered} 1: \\ \mathrm{有}\mathrm{标}\mathrm{号}\mathrm{无}\mathrm{根}\mathrm{树} \end{gathered}$$

$ans=n^{n-2}$

$$\begin{gathered} 2: \\ \mathrm{有}\mathrm{标}\mathrm{号}\mathrm{无}\mathrm{根}\mathrm{树} \end{gathered}$$

$ans=n^{n-1}$

$$\begin{gathered} 3: \\ \mathrm{无}\mathrm{标}\mathrm{号}\mathrm{有}\mathrm{根}\mathrm{树} \end{gathered}$$

设$f_i\mathrm{表}\mathrm{示}i\mathrm{个}\mathrm{点}\mathrm{的}\mathrm{方}\mathrm{案}\mathrm{数}，F(x)=\sum _i{f}_i{x}^i$
考虑由于无标号有根
那么对于子树每种大小相同形态无法区分
所以考虑所有大小为$k$的数构成的森林为
$(\sum _i{x}^{ik}{)}^{f_k}$
于是

$$F(x)=x\prod _{i=1}^{\mathrm{\infty }}(\frac{1}{1-x^k}{)}^{f_k}$$

同时取对后求导

$$\ln (F(x))=\ln x+\sum _{i=1}^{\mathrm{\infty }}{f}_k\ln (\frac{1}{1-x^k})$$$$\frac{F^{\prime }}{F}=\frac{1}{x}+\sum _{k=1}^{\mathrm{\infty }}{f}_{k}k\sum _{i=1}^{\mathrm{\infty }}{x}^{ik-1}$$$$x{F}^{\prime }=F+F\sum _{k=1}^{\mathrm{\infty }}{f}_{k}k\sum _{i=1}^{\mathrm{\infty }}{x}^{ik}$$

考虑对于$[x^n]$

$$f_{n}n=f_n+\sum _{j=1}^{n-1}{f}_i\sum _{k|n-j}k{f}_k$$$$(n-1)f_n=\sum _{i=1}^{n-1}{f}_i\sum _{j|n-i}j{f}_j$$

分治$NTT$并枚举倍数更新$i{f}_i$
复杂度$O(nlo{g}^{2}n)$

另外有一种$O(nlogn)$的推法

记

$$\begin{gathered} \xi (f(x))=\prod _i(\frac{1}{1-x^i}{)}^{f_i} \\ =\exp (\sum _{i=1}^{\mathrm{\infty }}{f}_i\sum _{j=1}^{\mathrm{\infty }}\frac{x^{ij}}{j}) \\ =\exp (\sum _{j=1}^{\mathrm{\infty }}\frac{f(x^j)}{j}) \end{gathered}$$

即上面最开始那玩意
那么就是$f(x)=x\xi (f(x))$
考虑用牛顿迭代求
已知$h(f_0)=f_0-x\xi (f_0)=0\mathrm{mod}{x}^n$
求$h(f)=0\mathrm{mod}{x}^{2n}$
那么就是$f=f_0-\frac{h(f_0)}{f^{\prime }(f_0)}$
考虑对于$\xi (f_0),\mathrm{记}g=\sum _{j=2}^{\mathrm{\infty }}\frac{f(x^j)}{j}$
由于是$\mathrm{mod}{x}^n\to \mathrm{mod}{x}^{2n}，\mathrm{所}\mathrm{以}g(x)\mathrm{可}\mathrm{以}\mathrm{看}\mathrm{做}\mathrm{是}\mathrm{已}\mathrm{知}\mathrm{的}\mathrm{常}\mathrm{量}$
那么$\xi (f_0)=\exp (f_0+g),{\xi }^{\prime }(f_0)=\exp (f_0+g)$

那么就是$f=f_0-\frac{f_0-x\xi (f_0)}{1-x\xi (f_0)}$
复杂度就是$O(nlogn)$的

$$\begin{gathered} 3: \\ \mathrm{无}\mathrm{标}\mathrm{号}\mathrm{无}\mathrm{根}\mathrm{树} \end{gathered}$$

考虑设$g_n$为答案
考虑容斥，对于一棵树看做用重心为根
减去所有其他的
$g_n=f_n-\sum _{i=1}^{\frac{n}{2}}{f}_i{f}_{n-i}$
但对于$n$为偶数的情况树可能有两个重心
这时候贡献是$(\genfrac{}{}{0ex}{}{f_{\frac{n}{2}}}{2})$而不是$f_{\frac{n}{2}}^2$
这个直接一次卷积即可

前面求$f$可以分治$NTT$做到$O(nlo{g}^{2}n)$
如果是用牛顿迭代就是$O(nlogn)$的

例题：$\mathrm{SPOJ}-\mathrm{PT}07\mathrm{D}$ $O(n^2)$
洛谷-无标号无根树计数 $O(nlo{g}^{2}n\mathrm{\&}nlogn)$

有标号$\mathrm{DAG}$计数

$$\begin{gathered} 1: \\ \mathrm{求}n\mathrm{个}\mathrm{点}\mathrm{有}\mathrm{标}\mathrm{号}\mathrm{的}\mathrm{有}\mathrm{向}\mathrm{无}\mathrm{环}\mathrm{图}(\mathrm{可}\mathrm{以}\mathrm{不}\mathrm{连}\mathrm{通}) \end{gathered}$$

设$f_i$为$i$个点的个数
枚举出度为$0$的点的个数
此时度数为$0$和其他点可以任意连边
但由于剩下的点也有出度为$0$的情况
容斥即可
那么

$$f_i=\sum _{j=1}^i(-1{)}^{j-1}(\genfrac{}{}{0ex}{}{i}{j})2^{j\ast (i-j)}{f}_{i-j}$$

复杂度$O(n^2)$
考虑用$NTT$优化上述$DP$

由于$2^{j(i-j)}$不好弄
有$j(i-j)=\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j{)}^2}{2}$
那么

$$2^{j(i-j)}=\frac{{\sqrt{2}}^{i^2}}{{\sqrt{2}}^{j^2}{\sqrt{2}}^{(i-j{)}^2}}$$

变形后原$DP$式变为

$$\frac{f_i}{{\sqrt{2}}^{i^2}i!}=\sum _{j=1}^i\frac{(-1{)}^{j-1}}{j!{\sqrt{2}}^{j^2}}\frac{f_{i-j}}{{\sqrt{2}}^{(i-j{)}^2}(i-j)!}$$

写成生成函数就是
$f=f\ast g+1$，则$f=\frac{1}{1-g}$
注意递推式$j$是从$1$开始所以$g$没有0次项
多项式求逆即可

模$998244353$下2的二次剩余有$11619517,882049182;$两个

$$\begin{gathered} 2： \\ \mathrm{求}n\mathrm{个}\mathrm{点}\mathrm{有}\mathrm{标}\mathrm{号}\mathrm{的}\mathrm{有}\mathrm{向}\mathrm{无}\mathrm{环}\mathrm{图}(\mathrm{图}\mathrm{必}\mathrm{须}\mathrm{是}\mathrm{弱}\mathrm{连}\mathrm{通}\mathrm{图}) \end{gathered}$$

考虑图必须弱联通
可以先求出$f$，然后容斥出$g$表示弱联通的答案
考虑枚举不连通时一号点所在连通块的大小减去
则$g_i=f_i-\sum _{j=1}^{i-1}(\genfrac{}{}{0ex}{}{i-1}{j-1})f_{i-j}{g}_j$
复杂度$O(n^2)$

考虑移项后有

$$\frac{g_i}{(i-1)!}+\sum _{j=1}^{i-1}\frac{f_{i-j}}{(i-j)!}\frac{g_j}{(j-1)!}=\frac{f_i}{(i-1)!}$$

设$F(x)=\sum _{i=1}^{\mathrm{\infty }}\frac{f_i}{i!}{x}^i,G(x)=\sum _{i=1}^{\mathrm{\infty }}\frac{f_i}{(i-1)!}{x}^i,P(x)=\sum _{i=1}^{\mathrm{\infty }}\frac{g_i}{(i-1)!}{x}^i$
那么就是$P+FP=G$
则$P=\frac{G}{1+F}$
多项式求逆即可
复杂度$O(nlogn)$

仙人掌计数

这个是有标号的

考虑先算有根的情况
考虑一个点可能在某些环里，也有可能与子仙人掌相连
把环上这个点删去后会有很多子仙人掌
于是考虑$\exp$
对于环正反顺序是相同的
所以得到$f(x)=x\exp (f(x)+\sum _{i\ge 2}\frac{f^i(x)}{2})$
考虑牛顿迭代

$$h(x)=f-x\exp (f+\frac{2f-f^2}{2-2f})$$

已知$h(f_0)\equiv 0\mathrm{mod}{x}^n$
求$h(f)\equiv 0\mathrm{mod}{x}^{2n}$
那么

$$f=f_0-\frac{h(f_0)}{h^{\prime }(f_0)}$$

对于$h(f(x))=xf(x)$这样的函数对$f$求导时将$x$看做常量

$$\begin{gathered} h^{\prime }(f_0)=1-(\frac{2f_0-f_0^2}{2-2f_0}{)}^{\prime }x\exp (\frac{2f_0-f_0^2}{2-2f_0}) \\ =1-\frac{f_0^2-2f_0+2}{2(f_0-1{)}^2}x\exp (\frac{2f_0-f_0^2}{2-2f_0}) \end{gathered}$$
于是

$$f=f_0-\frac{2f_0-2x\exp (\frac{2f_0-f_0^2}{2-2f_0})}{2-(1+\frac{1}{(f_0-1{)}^2})x\exp (\frac{2f_0-f_0^2}{2-2f_0})}$$

复杂度$O(nlogn)$

LOJ-仙人掌计数

---

无向连通图计数

考虑任意图是由无向连通图$\exp$得到
而任意图的个数为$2^{n\ast (n-1)/2}$个
直接求$\ln$即可

点双连通图计数

有标号
传送门

先求出$i$个点有根图个数
设其$EGF$为$F(x)$
设$b_i$表示$i+1$个点的点双个数，设$EGF$为$B(x)$
考虑对于一个无向有根连通图
根可能在多个点双内
删去根后会形成多个连通块
考虑将根以及所在的所有点双的边删去
则每个连通块都会变成若干个连通图
那么一个连通块的生成函数
枚举连通图个数就是$\sum _k\frac{b_k}{k!}H(x{)}^k$
设$B(x)=\sum _i\frac{b_i}{i!}{x}^i$
就有

$$F(x)=x{e}^{(B(F(x)))}$$

那么

$$\frac{F(x)}{e^{B(F(x))}}=x$$

设$F^{-1}(x)$为$F$的复合逆
那么有

$$F^{-1}(x)=\frac{x}{e^{B(x)}}$$$$B(x)=\ln (\frac{x}{F^{-1}(x)})$$

设$G(x)=\ln (\frac{F(x)}{x})$
则

$$G(F^{-1}(x))=B(x)$$

由拓展拉格朗日反演得

$$[x^n]B(x)=[x^n]G(F^{-1}(x))=\frac{1}{n}[x^{n-1}]G^{\prime }(x)(\frac{x}{F(x)})=\frac{1}{n}[x^{n-1}]G^{\prime }(x)(\frac{F(x)}{x}{)}^{-n}$$

多项式$\exp$求快速幂即可
复杂度$O(nlogn)$

---

边双连通图计数

有标号
传送门

仍然设$f(x)$表示有根图的$EGF$
设$b_i$表示$i$个点边双个数
考虑对于一个图
枚举根所在边双大小
删去后会剩下很多个无向联通子图
每个子图的根可以任意连向边双上任意一个点
那么就可以得到
$f(x)=\sum _{i\ge 1}\frac{b_i{x}^i}{i!}\exp (if(x))$
$=\sum _{i\ge 1}\frac{b_i{x}^i}{i!}\exp (f{)}^i=B(x\exp (f))$

设$g=x\exp (f)$
那么$f=B(g)$
取复合逆
$f(g^{-1})=B(x)$
$[x^n]B(x)=[x^n]f(g^{-1})=\frac{1}{n}[x^{n-1}]f^{\prime }(\frac{x}{g(x)}{)}^n=\frac{1}{n}[x^{n-1}]f^{\prime }\exp (-n\ast f)$
复杂度$O(nlogn)$