给定一张 (n) 个点，(m) 条边的图 (G)，计算他有多少个子图满足其强连通。答案对 (10^9+7) 取模。
(nle 15,mle frac{n(n-1)}{2})
( m Sol:)
感觉是开启了 DAG 计数/图计数 的先河？
先考虑一个暴力做法，注意到子图 (G') 是强连通图当且仅当缩点后有且仅有一个点。
反之其为 DAG，那么考虑计算图的总数减去缩点后是 DAG 的图的数量。
那么先考虑 DAG 计数。
设 (f_S) 表示点集 (S) 的 DAG 生成子图的数量，那么考虑：
不难发现其算重了，(f_T imes 2^{cnt_{T,S-T}}) 的真实含义为度数为 (0) 的点集至少为 (T) 的方案数。
于是可以使用容斥原理改写 DAG 计数：
接下来考虑强联通图计数，设 (g_S) 表示图 (S) 为强连通图的方案数，那么缩点为 DAG 即存在度为 (0) 点，那么不妨设 (H_{k,T}) 表示点集 (T) 的点构成 (k) 张强联通子图的方案数，且这些子图互不相交。
不难得到：
不难发现 (H_{k,T}) 其实与 (k) 的具体值无关，只关乎 (T) 模 (2) 的值，于是设 (G_{T}) 表示将图 (T) 拆成奇数个强连通块的方案数，(H_{T}) 表示将图 (T) 拆成偶数个强连通块的方案数，于是有：
问题瓶颈在于求解 (2^{cnt_{T,S-T}})，可以考虑枚举 (S)，然后枚举 (T) 同时沿途计算 (cnt_{T,S-T})
考虑预处理 (cnt_{x,S}) 即某个点到集合 (S) 的边数，那么就可以枚举 (S)，然后在枚举 (T) 的时候顺便将 (cnt_{T,S-T}) 给算出来了。复杂度是 (mathcal O(n^22^n+3^n))
如果保证图为无向图，那么可以借助 FWT 和 (cnt_{T,S-T}=cnt_{S}-cnt_{T}-cnt_{S-T}) 来进行子集 dp，复杂度可以做到 (mathcal O(n^22^n))
具体：
设 (g_S'=sum_{Tsubseteq S}(G_T-H_T) imes 2^{cnt_{T,S-T}} imes 2^{cnt_{T-S}})
于是就可以直接做了。