生成函数中某些计数问题

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

背包计数

$1:有
∑
_{1≤i≤n}
ai 种物品，体积为 i 的物品有 a_i 种。每种物品有无限个，求每种体积的方案数$

$$\prod_{i=1}^n(\sum_{j=0}^{\infty}x^{ij})^{a_i}=\exp(\sum_{i=1}^na_i\ln(\frac{1}{1-x^i}))$$

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

得到

$$\exp(\sum_{i=1}^{n}a_i\sum_{j=1}^{\infty}\frac{x^{ij}}{j}))$$

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

$2:有∑_{1≤i≤n}ai 种物品，体积为 i 的物品有 a_i 种。每种物品只有1个，求每种体积的方案数$

类似的生成函数为

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

后面的没区别

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

类似生成函数为

$$\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))$$

两部分也没区别

树的计数

$1:\\有标号无根树$

$ans=n^{n-2}$

$2:\\有标号无根树$

$ans=n^{n-1}$

$3:\\无标号有根树$

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

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

同时取对后求导

$$\ln(F(x))=\ln x+\sum_{i=1}^{\infty}f_k\ln(\frac{1}{1-x^k})$$ $$\frac{F'}{F}=\frac 1 x+\sum_{k=1}^{\infty}f_kk\sum_{i=1}^{\infty}x^{ik-1}$$ $$xF'=F+F\sum_{k=1}^{\infty}f_kk\sum_{i=1}^{\infty}x^{ik}$$

考虑对于$[x^n]$

$$f_nn=f_n+\sum_{j=1}^{n-1}f_i\sum_{k|n-j}kf_k$$ $$(n-1)f_n=\sum_{i=1}^{n-1}f_i\sum_{j|n-i}jf_j$$

分治$NTT$并枚举倍数更新$if_i$
复杂度$O(nlog^2n)$

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

记

$$\xi(f(x))=\prod_{i}(\frac{1}{1-x^i})^{f_i}\\=\exp(\sum_{i=1}^{\infty}f_i\sum_{j=1}^{\infty}\frac{x^{ij}}{j})\\ =\exp(\sum_{j=1}^{\infty}\frac{f(x^j)}j)$$

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

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

$3:\\无标号无根树$

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

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

例题：$\mathrm {SPOJ - PT07D}$ $O(n^2)$
洛谷-无标号无根树计数 $O(nlog^2n\&nlogn)$

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

$1:\\求n个点有标号的有向无环图(可以不连通)$

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

$$f_i=\sum_{j=1}^{i}(-1)^{j-1}{i\choose j}2^{j*(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{\sqrt2^{i^2}}{\sqrt2^{j^2}\sqrt2^{(i-j)^2}}$$

变形后原$DP$式变为

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

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

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

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

考虑图必须弱联通
可以先求出$f$，然后容斥出$g$表示弱联通的答案
考虑枚举不连通时一号点所在连通块的大小减去
则$g_i=f_i-\sum_{j=1}^{i-1}{i-1\choose 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}^{\infty}\frac{f_i}{i!}x^i,G(x)=\sum_{i=1}^{\infty}\frac{f_i}{(i-1)!}x^i,P(x)=\sum_{i=1}^{\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\geq2}\frac{f^i(x)}{2})$
考虑牛顿迭代

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

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

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

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

$h’(f_0)=1-(\frac{2f_0-f_0^2}{2-2f_0})’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})$
于是

$$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*(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)=xe^{(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'(x)(\frac{x}{F(x)})=\frac{1}{n}[x^{n-1}]G'(x)(\frac{F(x)}{x})^{-n}$$

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

---

边双连通图计数

有标号
传送门

仍然设$f(x)$表示有根图的$EGF$
设$b_i$表示$i$个点边双个数
考虑对于一个图
枚举根所在边双大小
删去后会剩下很多个无向联通子图
每个子图的根可以任意连向边双上任意一个点
那么就可以得到
$f(x)=\sum_{i\geq 1}\frac{b_ix^i}{i!}\exp(if(x))$
$=\sum_{i\geq 1}\frac{b_ix^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’(\frac{x}{g(x)})^n=\frac 1n[x^{n-1}]f’\exp(-n*f)$
复杂度$O(nlogn)$