QOJ 5437 Graph Completing
link
题意
给你一个 \(n\) 个点 \(m\) 条边的图，求多少种加边方案，使得该图变为一个边双联通图。必须保证该图始终为简单图，初始给出的图保证是简单图。
\(n \le 5000, m \le 10000\)。
思路
首先可以想到要边双缩点，容易发现缩点之后得到一棵树。
问题转换为连接树上若干点对，产生若干边双联通分量，最后要囊括所有点。
我们可以从环拓展到边双来看，一个环由树上 \(u\) 到 \(v\) 的路径和非树边 \((u, v)\) 构成，这可以使得 \(u\) 到 \(v\) 路径上的所有点、边都加入到边双中。
又边双联通关系是有传递性的，故只需要覆盖完所有的边就可以达到目标。
这个东西不好计数，反过来看，发现不覆盖一条边相当于把这条边断开，限制在某一范围内连边，这是容易计算的。
这启发我们考虑容斥，令 \(S_i\) 为满足 \(i\) 号边被覆盖的连边方案集合。
\[\begin{align*}
| \bigcap \limits _ i S_i | &= |U| - | \bigcup \limits _ i \overline{S_i} | \\
&= |U| - \sum \limits _ {T \subseteq S, T \ne \varnothing} (-1) ^ {|T| - 1} \times | \bigcap \limits _ {i \in T} \overline{S_i}|\\
&= |U| + \sum \limits _ {T \subseteq S, T \ne \varnothing} (-1) ^ {|T|} \times | \bigcap \limits _ {i \in T} \overline{S_i}|\\
&= \sum \limits _ {T \subseteq S} (-1) ^ {|T|} \times | \bigcap \limits _ {i \in T} \overline{S_i}|
\end{align*}
\]
问题转换为以 -1 的权值钦定一条边不被覆盖，也就是断开这条边，在剩下的连通块里操作。
考虑一个连通块内部操作的方案数（此时不限制是否覆盖边），这取决于能连的边个数，结果即为 2 的“能连边个数”幂。
\[\begin{align*}
能连边数 &= 连通块内总边数 - 已经连上的 \\
&= \binom {连通块大小} 2 - 所有 BCC 内部的边数之和 - 树边个数\\
&= \binom {连通块大小} 2 - 所以 BCC 内部的边数之和 - (连通块内 BCC 个数 - 1)\\
\end{align*}
\]
那么全局看，所有的连通块贡献积为：
\[\begin{align*}
&2 ^ {\left (\sum _ {连通块} { \binom {连通块大小} 2 } \right ) - (m - 树边个数) - 全局 BCC 个数 + 连通块个数} \\&= \frac {2 ^ {\left (\sum _ {连通块} {\binom {连通块大小} 2 + 1}\right ) }} {2 ^ {m + 1}}\end{align*}
\]
然后 dp 统计一下分子即可。\(f_{u, i}\) 表示 \(u\) 子树中，\(u\) 所在连通块大小为 \(i\) 时的贡献和。
\[\begin{align*}
f'_{u, i + j} &\leftarrow f_{u, i} \times f_{v, j} \\
f'_{u, i} &\leftarrow (-1) \times f_{u, i} \times \left( \sum _ j {f_{v, j} \times 2 ^ {\binom {j} {2} + 1}} \right)
\end{align*}
\]
把第二行那一坨东西设为 \(g_v\) 同步维护一下即可。
注意，计算连通块大小时，务必记得这里的点实际上是 BCC，应当带权。
代码
const int N = 5005;
const int mod = 998244353;
const int MAX_POW = N * (N - 1) / 2 + 2;int n, m;int pw[MAX_POW];vector<pair<int, int>> edge;
vector<int> gr[N];int low[N], dfn[N], dfncnt = 0;
int stk[N], top = 0;
bool in_stk[N];int bcc_cnt = 0;
int bcc_id[N];vector<int> tr[N];
int siz[N];
int f[N][N];
int g[N];
int tmp[N];void tarjan(int u, int fa){low[u] = dfn[u] = ++dfncnt;stk[++top] = u;in_stk[u] = 1;for(int v : gr[u]){if(v == fa) continue;if(!dfn[v]){tarjan(v, u);low[u] = min(low[u], low[v]);}else if(in_stk[v]){low[u] = min(low[u], dfn[v]);}}if(dfn[u] == low[u]){bcc_cnt++;do{bcc_id[stk[top]] = bcc_cnt;in_stk[stk[top]] = 0;siz[bcc_cnt]++;} while(stk[top--] != u);}
}int qpow(int a, int b){int res = 1;while(b){if(b & 1) res = 1ll * res * a % mod;a = 1ll * a * a % mod;b >>= 1;}return res;
}void dfs(int u, int fa){f[u][siz[u]] = 1;for(int v : tr[u]){if(v == fa) continue;dfs(v, u);rep(i, 1, siz[u]){rep(j, 1, siz[v]){tmp[i + j] = (tmp[i + j] + 1ll * f[u][i] * f[v][j] % mod) % mod;}}rep(i, 1, siz[u]){tmp[i] = (tmp[i] + (-1ll * f[u][i] * g[v]) % mod + mod) % mod;}rep(i, 1, siz[u] + siz[v]){f[u][i] = tmp[i];tmp[i] = 0;}siz[u] += siz[v];}rep(i, 1, siz[u]){g[u] = (g[u] + 1ll * pw[i * (i - 1) / 2 + 1] % mod * f[u][i] % mod) % mod;}
}void solve_test_case(){n = read(), m = read();pw[0] = 1;rep(i, 1, n * (n - 1) / 2 + 1){pw[i] = 1ll * pw[i - 1] * 2 % mod;}rep(i, 1, m){int u = read(), v = read();gr[u].push_back(v);gr[v].push_back(u);edge.push_back({u, v});}tarjan(1, 0);// rep(i, 1, n) deb(bcc_id[i]);rep(i, 0, m - 1){int u = edge[i].first, v = edge[i].second;u = bcc_id[u], v = bcc_id[v];if(u != v){tr[u].push_back(v);tr[v].push_back(u);}}dfs(1, 0);int ans = 0;rep(i, 1, siz[1]){ans = (ans + 1ll * f[1][i] * qpow(2, i * (i - 1) / 2 + 1) % mod) % mod;}ans = 1ll * ans * qpow(499122177, m + 1) % mod;write(ans);
}