3 条题解

  • 0
    @ 2024-10-25 21:46:59

    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
    上传者