直接 D p Dp Dp， O ( n 6 ) \mathcal{O}(n^6) O(n6)
如果从斯特林反演的角度来看呢？ 我们点 i i i 个连通块并强制其不联通，那么方案数其实是（记 n , e , c n,e,c n,e,c 分别为点数，边数，连通块数） ∑ i ( ∑ j = 1 i ( n j 2 ) m ) ( − 1 ) i ( i − 1 ) ! \sum_i\binom{\sum_{j=1}^i \binom{n_j}{2}}{m}(-1)^i(i-1)! ∑i(m∑j=1i(2nj))(−1)i(i−1)! 直接 D p Dp Dp 是 O ( n 5 ) \mathcal{O}(n^5) O(n5) 的
注意到我们并不需要记录 c ( G ) c(G) c(G) 我们只需要让其贡献 ( c ( G ) − 1 ) ! ( − 1 ) c ( G ) − 1 (c(G)-1)!(-1)^{c(G)-1} (c(G)−1)!(−1)c(G)−1 就可以了 枚举所有点的集合会统计 c ( G ) ! c(G)! c(G)!，那么我们枚举除1 号点外的任意子集就可以了 这样是 O ( n 4 ) \mathcal{O}(n^4) O(n4)
一些更多的思考： 我们设 F = ∑ i ≥ 1 x i ∑ j ≥ 0 ( ( i 2 ) j ) y j i ! F=\sum_{i\ge 1}\frac{x^i\sum_{j\ge 0}\binom{\binom{i}{2}}{j}y^j}{i!} F=∑i≥1i!xi∑j≥0(j(2i))yj 那么 ln ( 1 + F ) = ∑ i ≥ 1 F i i ! ( − 1 ) i − 1 ( i − 1 ) ! \ln(1+F)=\sum_{i\ge 1}\frac{F^i}{i!}(-1)^{i-1}(i-1)! ln(1+F)=∑i≥1i!Fi(−1)i−1(i−1)! 我们注意到 ∑ b i ∏ ( a i b i ) = ( ∑ a i ∑ b i ) \sum_{b_i}\prod \binom{a_i}{b_i}=\binom{\sum a_i}{\sum b_i} ∑bi∏(biai)=(∑bi∑ai) 所以说 F i F^i Fi 算实际上就是 ( ∑ ( i 2 ) m ) \binom{\sum \binom{i}{2}}{m} (m∑(2i))，这和之前斯特林反演的结论相符
当然这个还有很多应用，比如我们来 G x o r Gxor Gxor 这道题： 给出 m ≤ 50 m\le 50 m≤50 张图，问有多少方案选一个子集， x o r xor xor 起来的图恰好有 k k k 个连通块。
我们暴力搜出联通块划分，考虑 t t t 个连通块的系数是什么，设其生成函数为 C C C 则 C ( e z − 1 ) = z k k ! → C = ln ( 1 + z ) k k ! C(e^z-1)=\frac{z^k}{k!}\rightarrow C=\frac{\ln(1+z)^k}{k!} C(ez−1)=k!zk→C=k!ln(1+z)k
再比如说求 n n n 个点 k k k 个连通块的图的个数 设 G = ∑ i ≥ 1 2 ( i 2 ) z i i ! G=\sum_{i\ge 1}\frac{2^{\binom{i}{2}}z^i}{i!} G=∑i≥1i!2(2i)zi， F F F 为答案 那么 F = ln ( 1 + G ) k / k ! F=\ln(1+G)^k/k! F=ln(1+G)k/k! 如果用斯特林反演的角度来考虑，设容斥系数为 C C C 则 C ( G ) = F → C = ln ( 1 + z ) k k ! C(G)=F\rightarrow C=\frac{\ln(1+z)^k}{k!} C(G)=F→C=k!ln(1+z)k
Hint： s n , k = [ z n ] ( − ln 1 − z ) k / k ! s_{n,k}=[z^n](-\ln {1-z})^k/k! sn,k=[zn](−ln1−z)k/k!，所以说 ln ( 1 + z ) k = ( − 1 ) n − k s n , k \ln(1+z)^k=(-1)^{n-k}s_{n,k} ln(1+z)k=(−1)n−ksn,k 这与反转公式 ∑ i S n , i s i , m ( − 1 ) i − m = [ n = m ] \sum_{i}S_{n,i}s_{i,m}(-1)^{i-m}=[n=m] ∑iSn,isi,m(−1)i−m=[n=m] 得到的系数相符
