什么是网站版式,上海网站建设公司 珍岛,连锁销售平台,joomla建站教程传送门 解题思路 这道题就是求带标号的无向连通图个数#xff0c;首先考虑\(O(n^2)\)的做法#xff0c;设\(f_i\)表示有\(i\)个节点的无向连通图个数#xff0c;那么考虑容斥#xff0c;先把所有的无向图求出#xff0c;即为\(2^{C(n,2)}\)#xff0c;再减去不联通的情况…传送门 解题思路 这道题就是求带标号的无向连通图个数首先考虑\(O(n^2)\)的做法设\(f_i\)表示有\(i\)个节点的无向连通图个数那么考虑容斥先把所有的无向图求出即为\(2^{C(n,2)}\)再减去不联通的情况而计算不联通情况时可以枚举\(1\)号点这个联通块的大小就有方程 \[f_i2^{C_i^2}-\sum\limits_{j1}^{i-1}C_{i-1}^{j-1}2^{C^2_{i-j}}f_j\] 发现这样的时间复杂度为\(O(n^2)\)的无法通过本题。考虑优化我们设法把左右两边的\(f\)合并可以给式子同时除一个\((i-1)!\)可得\[\frac{f_i}{(i-1)!}\frac{2^{C_i^2}}{(i-1)!}-\sum\limits_{j1}^{i-1}\frac{2^{C^2_{i-j}}f_j}{(j-1)!(i-j)!}\] 发现右边假设\(j\)枚举到\(i\)正好是左边那么就移项。\[\sum\limits_{j1}^i\frac{C^{2}_{i-j}f_j}{(j-1)!(i-j)!}\frac{2^{C_i^2}}{(i-1)!}\] 右边是卷积的形式\[\sum\limits_{j1}^i\frac{f_j}{(j-1)!}*\frac{2^{C^2_{i-j}}}{(i-j)!}\frac{2^{C^2_i}}{(i-1)!}\] 设\(A\sum\limits_{i1}^n\dfrac{f_i}{(i-1)!}x^i\)\(B\sum\limits_{i0}^{n-1}\dfrac{2^{C_i^2}}{i!}x^i\)\(C\sum\limits_{i1}^n\dfrac{2^{C_i^2}}{(i-1)!}x^i\)则\[A*BC\]\[AC*B^{-1}\] 多项式求逆即可时间复杂度\(O(nlogn)\) 转载于:https://www.cnblogs.com/sdfzsyq/p/10432954.html
