简单环（状压 dp，详细注释）

简单环

参考博客：牛客网 Wannafly挑战赛17 C-简单环 状压dp

题目描述

给定一张n个点m条边的无向图，求出图中所有简单环的数量。(简单环：简单环又称简单回路，图的顶点序列中，除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路叫简单回路。或者说，若通路或回路不重复地包含相同的边，则它是简单的)

输入描述:

第一行三个数n m k (k在输出描述中提到)
接下来m行每行两个数u，v表示u到v之间存在一条边（无重边）

输出描述:

输出k行每行1个整数
第i个数表示长度%k==i-1的简单环的数量（对998244353取模）
(只记录长度大于2的简单环的数量)

输入

4 6 3
1 2
2 3
3 4
4 1
2 4
1 3

输出

4
3
0

备注:

n<=20
m<=n*(n-1)/2
k<=n

思路

把路径转化为二进制状态，设置一个数组 f[i][j] 表示路径终点为 j ，二进制下状态为i的数目，为了避免重复，可以把 i 最小位的 1 设为起点，枚举状态和终点，若终点到起点有直接连接则为答案。最后每条环仍会重复计算两次，需要求除法逆元去重。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>

using namespace std;
#define ll long long
// n 个点，m 条边，k 行输出
int n, m, k;
//记录能走的路
bool vis[21][21];
//f[i][j]保存路径终点为 j，二进制下状态为 i 的个数
int f[1 << 21][21];
//ans[] 记录最后的结果，只用 0 ~ k-1
//len[] 记录不同 i 长度环的个数
int ans[21], len[41];
const int mod = 998244353;

//返回二进制下最低位 1 的位置
int lowbit(int x) {
    return x & (-x);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    //输入边
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x != y) {
            vis[x][y] = vis[y][x] = true;
        }
    }
    //初始化 f[][]
    for (int i = 1; i <= n; i++) {
        f[1 << i][i] = 1;
    }
    for (int i = 2; i < 1 << (n + 1); i += 2) {
        //获取 s
        int st = lowbit(i), s;
        for (int j = 1; j <= n; j++) {
            if (1 << j == st) {
                s = j;
                break;
            }
        }
//        cout<<"i: "<<i<<" "<<"  s: "<<s<<endl;
        for (int j = 1; j <= n; j++) {
            if (f[i][j]) {
//                cout<<"有初始值，f["<<i<<"]["<<j<<"]，初始值为："<<f[i][j]<<"\n";
                //此路可走
                if (vis[j][s]) {
                    //__builtin_popcount() 计算二进制中有多少个 1
                    len[__builtin_popcount(i)] += f[i][j];
                    len[__builtin_popcount(i)] %= mod;
//                    cout<<"此路可走，vis["<<j<<"]["<<s<<"]\n";
//                    cout<<"更新后，len["<<__builtin_popcount(i)<<"] = "<<len[__builtin_popcount(i)]<<endl;
                }
                //从 s+1 开始枚举，避免重复计算路径
                for (int k = s + 1; k <= n; k++) {
                    // !(i & (1 << k))：没有经过这个点
                    if (vis[j][k] && !(i & (1 << k))) {
                        f[i ^ (1 << k)][k] += f[i][j];
                        f[i ^ (1 << k)][k] %= mod;
                    }
                }
            }
        }
    }

    //只记录长度大于 2 的简单环的数量
    for (int i = 3; i <= n; i++) {
        ans[i % k] += len[i];
        ans[i % k] %= mod;
    }
    //每个环仍旧会被重复计算两次
    for (int i = 0; i < k; i++) {
        printf("%d\n", ans[i] * ((ll) (mod + 1) / 2) % mod);
    }
    return 0;
}
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82