题解：AT_abc411_g [ABC411G] Count Cycles

· · 题解

前言

相似原题 CF11D，本质上就是一题。

题解

首先观察到点数 N \le 20 极少，不难想到状态压缩，于是我们可以用 S 表示当前将要成环的点集，但是我们发现，仅仅抽象出一个环上的点集，我们并不知道从哪里开始，而且一个环有多种表示方式，这就给我们状态转移和合法环计算带来了麻烦，于是，我们可以考虑一种叫做按秩转移技巧，也就是我们考虑每个状态 \operatorname{lowbit}(S) 作为起点，也就是标号最小的点表示，这样顺时针与逆时针会被计算两次，最后除去即可。

那么我们就可以设 f_{s, i} 表示状态为 S 从 \operatorname{lowbit}(S) 出发，到第 i 个点的方案数，考虑如何转移，对于当前状态，我们可以枚举 i 的出边的端点，如果该标号点大于 \operatorname{lowbit}(S) 或者该点这个状态已经存在，我们就跳过；等于 \operatorname{lowbit}(S) 时，这个环就形成了闭合，乘上边数统计答案即可；那么再就是一个全新的点 t，那么就转移状态为 ：

f_{s + (1 << t), t} = f_{s + (1<<t),t} + f_{s, i} \times g_{i, t}

其中，g_{i, t} 表示 i 与 t 之间的边数。

到这里，本题基本上也就做完了，不过需要注意的是这样统计会有一条边连接两个点的情况，所以答案减去边数再除以 2 即可。

时间复杂度

O(2 ^ NN ^ 2)

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 21, P = 998244353;
int f[1 << N][21];
int st[N][N], n, m;
int ans;

int lowbit(int x)
{
    return x & -x;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        a -- , b -- ;
        st[a][b] ++ , st[b][a] ++ ;
    }
    for (int i = 0; i < n; i ++ ) f[1 << i][i] = 1;
    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            if (!f[i][j]) continue;
            for (int k = 0; k < n; k ++ )
            {
                if (!st[k][j] || lowbit(i) > (1 << k)) continue;
                if (lowbit(i) == (1 << k)) ans = (ans + f[i][j] * st[k][j] % P) % P;
                else if (!(i & (1 << k))) f[i | (1 << k)][k] = (f[i | (1 << k)][k] + f[i][j] * st[k][j] % P) % P;
            }
        }
    cout << (((ans - m) % P + P) * 499122177 % P) % P;
    return 0;
}