解题思路
这道题就是求带标号的无向连通图个数，首先考虑(O(n^2))的做法，设(f_i)表示有(i)个节点的无向连通图个数，那么考虑容斥，先把所有的无向图求出，即为(2^{C(n,2)})，再减去不联通的情况，而计算不联通情况时可以枚举(1)号点这个联通块的大小，就有方程
$$f_i=2{C_i2}-sumlimits_{j=1}{i-1}C_{i-1}{j-1}2{C2_{i-j}}f_j$$
发现这样的时间复杂度为(O(n^2))的，无法通过本题。考虑优化，我们设法把左右两边的(f)合并，可以给式子同时除一个((i-1)!)，可得
[frac{f_i}{(i-1)!}=frac{2^{C_i^2}}{(i-1)!}-sumlimits_{j=1}^{i-1}frac{2^{C^2_{i-j}}f_j}{(j-1)!(i-j)!}
]
发现右边假设(j)枚举到(i)正好是左边，那么就移项。
[sumlimits_{j=1}^ifrac{C^{2}_{i-j}f_j}{(j-1)!(i-j)!}=frac{2^{C_i^2}}{(i-1)!}
]
右边是卷积的形式
[sumlimits_{j=1}^ifrac{f_j}{(j-1)!}*frac{2^{C^2_{i-j}}}{(i-j)!}=frac{2^{C^2_i}}{(i-1)!}
]
设(A=sumlimits_{i=1}^ndfrac{f_i}{(i-1)!}x^i)，(B=sumlimits_{i=0}^{n-1}dfrac{2^{C_i^2}}{i!}x^i)，(C=sumlimits_{i=1}^ndfrac{2^{C_i^2}}{(i-1)!}x^i)，则
[A*B=C
]
[A=C*B^{-1}
]
多项式求逆即可，时间复杂度(O(nlogn))