Gym 102361F - Forest Program

发表于 更新于 分类于 阅读次数：

题目链接：Gym 102361F

考虑每个简单环内至少取一条边，如果一个简单环有 \(x\) 条边，那么这个简单环的方案数为 \(\sum_{i=1}^{x} {x \choose i} = 2^x - 1\)，对于非简单环上的边（即剩余的边）如果有 \(r\) 条，那么方案数为 \(\sum_{i=1}^{r} {r \choose i} = 2^r\)，最后分步计数即可。

需要注意的是，这里没有保证整张图是联通的，只保证每个联通块是一个仙人掌，所以不能只DFS一个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P = 998244353;
inline LL getPow(LL x, LL y) {
    LL ret = 1;
    while (y) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
const int MAX_N = 300000 + 5;
int n, m;
vector <int> g[MAX_N];
vector <int> cir;
stack <int> stk;
int pos[MAX_N];
int ins[MAX_N];
int vis[MAX_N];
int eCnt;
void dfs(int x, int fa) {
    // printf("call dfs(x = %d, fa = %d)\n", x, fa);
    stk.push(x);
    ins[x] = 1;
    pos[x] = stk.size();
    for (auto const &e: g[x]) {
        if (e == fa) {
            continue;
        } else if (ins[e]) {
            cir.push_back(pos[x] - pos[e] + 1);
            eCnt += (pos[x] - pos[e] + 1);
        } else if (!vis[e]) {
            dfs(e, x);
        }
    }
    stk.pop();
    ins[x] = 0;
    vis[x] = 1;
}
int main() {
    scanf("%d%d", &n, &m);
    // build graph
    int u, v;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // solve
    // dfs(1, -1);
    for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, -1);
    LL ans = 1;
    for (unsigned i = 0; i < cir.size(); ++i) {
        LL con = (((getPow(2, cir[i]) - 1) % P) + P) % P;
        ans = ans * con % P;
    }
    ans = ans * getPow(2, m - eCnt) % P;
    printf("%lld\n", ans);
    return 0;
}