logoChat01.ai

### Problem Statement There is an undirected grap...

बनाया गया: 21 जून 2025

का उपयोग करके उत्तर दिया गया O3 द्वारा Chat01

प्रश्न

Problem Statement

There is an undirected graph GG with NN vertices and MM edges. GG does not contain self-loops, but may contain multi-edges. Vertices are numbered from 11 to NN, and edges are numbered from 11 to MM, with edge ii connecting vertices Ui,ViU_i,V_i.

Find the number, modulo 998244353998244353, of cycles contained in GG.

More formally, find the number, modulo 998244353998244353, of subsets {e1,e2,…,ek}⊆{1,2,…,M} (k≥2)\lbrace e_1,e_2,\dots,e_k\rbrace \subseteq \lbrace 1,2,\dots,M\rbrace\ (k\geq 2) of the given edge set that satisfy the following condition.

  • There exists a permutation (e1′,e2′,…,ek′)(e_1',e_2',\dots,e_k') of (e1,e2,…,ek)(e_1,e_2,\dots,e_k) and a vertex sequence (v1,v2,…,vk)(v_1,v_2,\dots,v_k) such that all of the following hold:
    • v1,v2,…,vkv_1,v_2,\dots,v_k are pairwise distinct;
    • For all j (1≤j≤k)j\ (1\leq j\leq k), edge ej′e_j' connects vertices vj,v(j mod k)+1v_j,v_{(j\bmod k) + 1}.C++代码

विचार

It seems like I’m investigating how to count cycles in a graph using dynamic programming or bitmasking, especially for N ≤ 20. My initial search didn’t give me useful results, so I'll consider explaining the algorithm step-by-step. The key idea might be to enumerate cyclic subsets with BFS, using recursion and backtracking. Given time constraints, I might also focus on how to handle simple cycles up to 10^5, so I can present an approach that's easier to follow.

It looks like I’m planning to write C++ code to count cycles in a graph with N vertices (up to 20) using bitmask enumeration. The method involves using dynamic programming (DP) and an adjacency matrix to track connections between vertices. I’m thinking of using a classic DP approach to count Hamiltonian cycles, expanding paths and avoiding duplicates by keeping track of the smallest start vertex. I might need to handle edge multiplicities and ensure that parallel edges are properly counted. The final result will be taken modulo 998.

Thought for 2m 34s

उत्तर

下面给出一种 可以正确计数任意简单环（允许长度 = 2 的“平行边环”） 的通用做法。
它基于「起点固定 + 位运算子集 DP」——当 N≤20 左右时完全能在 2 秒内通过；
如果 N 很大，这个问题在一般图上属于 #P-hard，任何已知算法都需要指数时间。

思路概览

  1. 建邻接矩阵（带重数）

    text
    adj[u][v] = 与 u,v 之间的平行边条数   (u≠v)

    由于图无自环，adj[u][u] = 0。

  2. 按照最小编号顶点去重
    对每个起点 s：

    • 只考虑所有包含 s 的顶点集合 mask，并保证 s 是集合中编号最小的顶点。
      这样可保证每条无向简单环只被统计一次。
    • 令 dp[mask][v] 表示：

      “从 s 出发，经过 mask 中所有点一次且仅一次，最终停在 v（v∈mask）” 的方案数
      （路线按边 顺序 区分，同一条边的多条平行边也区分）。

  3. 状态转移

    text
    初始: dp[1<<s][s] = 1
枚举 mask, 枚举末点 v∈mask
    枚举下一点 u∉mask 且 adj[v][u] > 0
        dp[mask | (1<<u)][u] += dp[mask][v] * adj[v][u]

    复杂度 O(3^N)（见 USACO-Guide Bitmask-DP 教程 usaco.guide）。

  4. 收尾形成环
    当 mask 至少含 2 个顶点且 adj[v][s] > 0 时，

    ans += dp[mask][v] * adj[v][s]

    这里再乘一次平行边条数。

  5. 取模
    每一步都对 MOD = 998244353 取模即可。

正确性说明

  • 顶点序列 s → … → v → s 中每个顶点至多出现一次，因此得到的是简单环。
  • 由于固定 s 为环中最小编号顶点，且构造过程中从未再回到比 s 小的顶点，所以任何简单环恰好被统计一次。
  • 若 u,v 之间有 c 条平行边，则环中可以自由选择这 c 条中的任意一条，所以每对顶点相乘时乘上 adj[u][v] 可计入所有可能。

复杂度

符号含义规模
N顶点数≤ 20 – 22 时可跑
M边数 (含重)≤ 400k (任意)
  • 状态数 2^N · N
  • 对每个状态再枚举一个“下一顶点” u，摊到平均 ≈ N/2
    → 总体 O(N · 2^N) ≈ 3^N，N=20 约 20 × 1 048 576 ≈ 2 × 10^7 次转移，1 秒内可过。
  • 记忆使用 vector<int>/uint32_t 储存非零 dp 列即可，空间 O(N·2^N)。

参考实现（C++17）

cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int addmod(int a, int b) { int s = a + b; return s >= MOD ? s - MOD : s; }
int mulmod(long long a, long long b) { return int((a * b) % MOD); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;

    /* 邻接矩阵，记录平行边条数 */
    vector<vector<int>> adj(N, vector<int>(N, 0));
    for (int i = 0, u, v; i < M; ++i) {
        cin >> u >> v; --u; --v;
        if (u == v) continue;          // 无自环
        ++adj[u][v];
        ++adj[v][u];
    }

    long long fullStates = 1LL << N;
    /* dp 是一个 vector<unordered_map<int,int>>，也可用平面数组 */
    vector<vector<int>> dp(fullStates);  // sparse：dp[mask][v] 按 v 索引
    long long answer = 0;

    for (int s = 0; s < N; ++s) {
        /* 清空与 s 相关的状态 */
        for (long long m = 0; m < fullStates; ++m) dp[m].clear();

        long long startMask = 1LL << s;
        dp[startMask].resize(N);
        dp[startMask][s] = 1;

        for (long long mask = startMask; mask < fullStates; ++mask) {
            if (!(mask & startMask)) continue;        // 必须含 s
            /* 找到 mask 中最大的顶点索引，加速子集枚举（可选） */

            for (int v = 0; v < N; ++v) {
                int ways = (mask < fullStates && v < (int)dp[mask].size()) ? dp[mask][v] : 0;
                if (!ways) continue;
                /* 尝试闭环 */
                if (__builtin_popcountll(mask) >= 2 && adj[v][s])
                    answer = addmod(answer, mulmod(ways, adj[v][s]));

                /* 向外扩展 */
                for (int u = s + 1; u < N; ++u) if (!(mask & (1LL << u)) && adj[v][u]) {
                    long long nmask = mask | (1LL << u);
                    if (dp[nmask].empty()) dp[nmask].resize(N);
                    dp[nmask][u] = addmod(dp[nmask][u], mulmod(ways, adj[v][u]));
                }
            }
        }
    }

    cout << (answer % MOD) << '\n';
    return 0;
}

说明

  • 稀疏存储：dp[mask] 只在需要时分配；
    若 N≤20，内存 < 80 MB。
  • 起点固定 + 起点最小：向外扩展时只允许加入 u > s，即可确保不重复计数；
    若去掉这句话，需额外在闭环时除以 2 来消重方向。
  • 环长 2 处理：当 mask 仅含两个顶点 (s,v) 时，仍能通过 “闭环” 语句被正确统计。

适用范围

  • N ≤ 20 – 22：本算法最快最简单。
  • N ≫ 20 且要计数全部简单环：这在理论上是 #P-complete，
    没有比指数级更好的算法；竞赛题一般会附加额外限制（如度数≤2、图是族森林、图是格点等）。
    若你的实际数据规模更大，请先确认题目是否隐藏了特殊结构，或改用 Monte-Carlo / 近似算法。

祝 AC!

इस प्रश्नोत्तर को साझा करें