3 条题解
-
0
Answer is here!
#include<bits/stdc++.h> using ll = long long; constexpr ll mod = 998244353; const int maxn = 1e6 + 10; int n, N; ll pw[maxn]; std::vector<int> G[maxn], to[maxn]; int low[maxn], dfn[maxn], dt, stk[maxn], top; int siz[maxn]; void dfs1(int u) { low[u] = dfn[u] = ++dt, stk[++top] = u; for (int v : G[u]) { if (dfn[v]) low[u] = std::min(low[u], dfn[v]); else { dfs1(v), low[u] = std::min(low[u], low[v]); if (dfn[u] == low[v]) { N++, to[u].push_back(n + N), to[n + N].push_back(u); int t; do {t = stk[top--]; to[t].push_back(n + N), to[n + N].push_back(t);} while (t != v); siz[n + N] = to[n + N].size(); } } } } ll f[maxn], g[maxn]; void dfs2(int u, int fa) { if (u != 1 && to[u].size() == 1) return f[u] = g[u] = 1, void(); ll h[3] = {1, 0, 0}; for (int v : to[u]) { if (v == fa) continue; dfs2(v, u); h[2] = (h[2] * (g[v] + 1) + h[1] * g[v]) % mod, h[1] = (h[1] + h[0] * g[v]) % mod; } if (u > n) f[u] = pw[siz[u] - 1] * h[2] % mod, g[u] = (pw[siz[u] - 1] * h[1] + f[u]) % mod; else f[u] = (2ll * h[2] + h[1] + h[0]) % mod, g[u] = (h[1] + f[u]) % mod; } int main() { int m; scanf("%d%d", &n, &m); for (int i = pw[0] = 1; i <= n; i++) (pw[i] = pw[i - 1] << 1) >= mod && (pw[i] -= mod); for (int x, y; m--; ) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x); dfs1(1); dfs2(1, 0); ll ans = 0; for (int i = 1; i <= n + N; i++) (ans += f[i]) %= mod; printf("%lld\n", (2ll * ans + 1ll) % mod); return 0; }
thank you!
信息
- ID
- 4
- 时间
- 3000ms
- 内存
- 1024MiB
- 难度
- 7
- 标签
- 递交数
- 139
- 已通过
- 25
- 上传者