题解：统计存在欧拉回路的子图数量

问题分析

题目要求统计所有满足以下条件的子图数量：

1. 子图包含若干亭子（顶点）和道路（边）；
2. 子图中存在欧拉回路，即能从某顶点出发，不重复不遗漏地走完所有边并返回起点。

欧拉回路的判定条件为：

• 子图连通；
• 子图中所有顶点的度数均为偶数。

核心思路

1. 枚举顶点集：由于顶点数 ( n \leq 20 )，可用二进制掩码（bitmask）枚举所有非空顶点集 ( V )。
2. 筛选边集：对每个顶点集 ( V )，筛选出所有端点均在 ( V ) 中的边，构成边集 ( E_V )。
3. 计算有效边子集：
   • 度数全偶的边子集（记为 ( g(V) )）：满足 ( V ) 中所有顶点度数为偶数的 ( E_V ) 子集数量。
   • 连通且度数全偶的边子集（记为 ( f(V) )）：在 ( g(V) ) 中减去不连通的边子集数量（用容斥原理）。
4. 汇总结果：所有 ( f(V) ) 的和即为答案。

算法实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 20;
const int MAXMASK = 1 << MAXN;

vector<pair<int, int>> edges;
int n, m;
int f[MAXMASK], g[MAXMASK];
int pow2[200]; // 预处理2的幂次，最多用到m=190

// 预处理2的幂次
void precompute_pow2() {
    pow2[0] = 1;
    for (int i = 1; i < 200; ++i) {
        pow2[i] = (pow2[i-1] * 2LL) % MOD;
    }
}

int main() {
    precompute_pow2();
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--; // 转为0-based
        edges.emplace_back(u, v);
    }

    // 枚举所有非空顶点集V（bitmask）
    for (int V = 1; V < (1 << n); ++V) {
        int k = __builtin_popcount(V); // V中顶点数量
        vector<pair<int, int>> E_V;
        for (auto& e : edges) {
            int u = e.first, v = e.second;
            if ((V & (1 << u)) && (V & (1 << v))) {
                E_V.push_back(e);
            }
        }
        int m_V = E_V.size();

        if (m_V == 0) {
            // 无边的情况：只有单个顶点时f=1，否则f=0
            f[V] = (k == 1) ? 1 : 0;
            g[V] = 1; // g(V) = 2^0 = 1
            continue;
        }

        // 计算V在E_V中的连通分量
        vector<int> nodes;
        for (int i = 0; i < n; ++i) {
            if (V & (1 << i)) {
                nodes.push_back(i);
            }
        }

        // 并查集找连通分量
        unordered_map<int, int> parent;
        for (int u : nodes) parent[u] = u;
        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };
        auto unite = [&](int x, int y) {
            x = find(x), y = find(y);
            if (x != y) parent[y] = x;
        };
        for (auto& e : E_V) {
            unite(e.first, e.second);
        }

        // 收集连通分量的bitmask
        unordered_map<int, int> comp_map;
        for (int u : nodes) {
            int root = find(u);
            comp_map[root] |= (1 << u);
        }
        vector<int> components;
        for (auto& p : comp_map) {
            components.push_back(p.second);
        }
        int c = components.size(); // 连通分量数量

        // 计算g(V) = 2^(m_V - (k - c))
        int exponent = m_V - (k - c);
        g[V] = pow2[exponent];

        // 计算f(V) = g(V) - sum(f(U) * g(W))，其中U是连通分量的非空真子集
        int sum = 0;
        if (c >= 2) {
            // 枚举所有非空真子集（s从1到(1<<c)-2）
            for (int s = 1; s < (1 << c) - 1; ++s) {
                int U = 0;
                for (int i = 0; i < c; ++i) {
                    if (s & (1 << i)) {
                        U |= components[i];
                    }
                }
                int W = V ^ U;
                sum = (sum + 1LL * f[U] * g[W]) % MOD;
            }
        }
        f[V] = (g[V] - sum + MOD) % MOD;
    }

    // 累加所有f(V)
    int ans = 0;
    for (int V = 1; V < (1 << n); ++V) {
        ans = (ans + f[V]) % MOD;
    }
    cout << ans << endl;

    return 0;
}

关键细节

1. 状态压缩：用bitmask表示顶点集，高效枚举所有可能的子图顶点。
2. 连通分量计算：用并查集确定顶点集 ( V ) 在边集 ( E_V ) 中的连通分量，用于计算 ( g(V) ) 和容斥求和。
3. 容斥原理：通过减去非连通子图的数量，从度数全偶的边子集中筛选出连通的边子集（即 ( f(V) )）。

该算法利用状态压缩和容斥原理，高效处理 ( n \leq 20 ) 的约束，时间复杂度主要由顶点集枚举和连通分量处理决定，约为 ( O(2^n \cdot 2^c) )（( c ) 为连通分量数），在题目范围内可行。