【题解】P5827 点双连通图计数

📅 2026/7/18 22:17:47 👁️ 阅读次数 📝 编程学习
【题解】P5827 点双连通图计数

考虑有根连通图 EGF 是 \(C\)
那么考虑去掉 \(C\) 的根,那么用 exp 生成方点,而方点的 EGF 可以用 \(B=\sum_{i=1}^\infty b_{i+1}\frac{x^i}{i!}\) 表示。
那么也就是 \(C(x)=x\exp(B(C(x)))\)

那么 \(\ln(\frac{C(x)}{x})=B(C(x))\Rightarrow \ln(\frac{C(C^{\left\langle -1 \right\rangle}(x))}{C^{\left\langle -1 \right\rangle}(x)})=B(x)\)
\(H(x)=\ln(\frac{C(x)}{x})\),于是 \([x^{n}]H(C^{\left\langle -1 \right\rangle}(x))=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{C(x)})^n\)
\((\frac{x}{C(x)})^n=\exp(-n\ln\frac{C(x)}{x})=\exp(-nH(x))\)