Subtask分值𝑛,𝑚 𝑇 𝐴,𝐵,𝐶 1 12 ≤4 2 12 ≤8 3 12...

Question

Subtask分值𝑛,𝑚 𝑇 𝐴,𝐵,𝐶
1 12 ≤4
2 12 ≤8
3 12 ≤12
4 12 ≤20
5 12 ≤40 =1 =1
6 20 ≤40 =1
7 20 ≤50
做你会做的尽可能多的分数

Answer 1

下面这题本体（叫 Demon）信息比较少，而且“好序列”的定义在图里是有些歧义的。我按字面理解整理出一个可拿部分分的解法，能稳过最小子任务（n,m≤4），并且对 A=B=C 的大子任务能直接 O(1) 输出答案；另外根据题面“好序列=开始时图是双连通(连通且 f(G)=0)”的直译，T=1 在 n≥2 时答案恒为 0（因为初始是 n 个孤点，不连通）。

如果你的题库评测与这一定义一致，这份代码能覆盖下表里的分数块：

n,m ≤ 4（暴力枚举，精确）：✅
A=B=C（题面第 2 问 / 第 1 问都可，直接公式）：✅
T=1 且 n≥2（按直译恒 0）：✅

其余情形（尤其一般的 T=2 且 A,B,C 不相同）要做完整的期望/计数需要跟踪双连通块与桥的演化，工程量较大，这里未实现。

思路概要

图是多重图并允许自环；自环永远不是桥。
对于一条无向边 $(u,v)$ $(u, v)$ （ $u\ne v$ $u \neq = v$ ）：
- 若它是该对点的唯一一条边，并且在去重后的简单图里是桥，则它记作 1 条桥；
- 若该对点已有平行边（多于 1 条），则这一对点的所有边都不是桥。
每次操作比较 $f(G)$ $f (G)$ 的增减：
- 增加 → $X+=A$
- 不变 → $X+=B$
- 减少 → $X+=C$

我们提供两条计算路径：

精确枚举（小数据）
对所有 $\frac{n(n+1)}{2}$ 种“点对（含自环）”在 m 步上的选择做 DFS，维护邻接多重矩阵；每步用 Tarjan 在“去重后的简单图”上求桥，结合该对点的重数是否为 1 来得到多重图的桥数，从而得到 $X$ 的增量。

这个方法在 $n,m\le 4$ 时完全可行（最多 $10^4$ 条序列）。

A=B=C 的快速公式
若 $A=B=C$ ，则不管图如何变化，每步都给 $X$ 加同一个数。于是

\sum_{\text{所有序列}} X = \big(m\cdot A\big)\times \Big(\frac{n(n+1)}{2}\Big)^m \pmod{998244353}.

（T=1 与 T=2 均成立；若按题面直译，T=1 且 $n\ge2$ 时“好序列数”为 0，则答案为 0。）

代码（C++17，能直接提交）

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

static inline long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

struct Solver {
    int T, n, m;
    long long A, B, C;

    // mult[u][v] (u<=v): multiplicity; loops: u==v
    vector<vector<int>> mult;

    // --- build simple graph & count bridges for multigraph ---
    int bridge_count() {
        // Build simple graph ignoring loops; keep an id for every undirected simple edge
        vector<vector<pair<int,int>>> g(n);
        vector<pair<int,int>> edges; // (u,v) with u<v
        vector<vector<int>> id(n, vector<int>(n, -1));

        for (int u = 0; u < n; ++u) {
            for (int v = u + 1; v < n; ++v) {
                if (mult[u][v] > 0) {
                    int eid = (int)edges.size();
                    edges.push_back({u, v});
                    id[u][v] = id[v][u] = eid;
                    g[u].push_back({v, eid});
                    g[v].push_back({u, eid});
                }
            }
        }

        int E = (int)edges.size();
        vector<int> disc(n, -1), low(n, -1);
        vector<char> isBridge(E, 0);
        int timer = 0;

        function<void(int,int)> dfs = [&](int u, int peid) {
            disc[u] = low[u] = ++timer;
            for (auto [v, eid] : g[u]) {
                if (eid == peid) continue;
                if (disc[v] == -1) {
                    dfs(v, eid);
                    low[u] = min(low[u], low[v]);
                    if (low[v] > disc[u]) {
                        isBridge[eid] = 1; // simple-graph bridge
                    }
                } else {
                    low[u] = min(low[u], disc[v]);
                }
            }
        };
        for (int i = 0; i < n; ++i) if (disc[i] == -1) dfs(i, -1);

        // multigraph: only edges with multiplicity == 1 AND simple-bridge contribute
        int cnt = 0;
        for (int eid = 0; eid < E; ++eid) {
            auto [u, v] = edges[eid];
            if (mult[u][v] == 1 && isBridge[eid]) ++cnt;
        }
        return cnt;
    }

    // connected? (ignoring loops; isolated vertices count as separate components)
    bool connected_simple() {
        vector<vector<int>> adj(n);
        for (int u = 0; u < n; ++u)
            for (int v = u + 1; v < n; ++v)
                if (mult[u][v] > 0) {
                    adj[u].push_back(v);
                    adj[v].push_back(u);
                }

        vector<int> vis(n, 0);
        int comps = 0;
        for (int i = 0; i < n; ++i) if (!vis[i]) {
            ++comps;
            queue<int> q; q.push(i); vis[i] = 1;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) if (!vis[v]) vis[v] = 1, q.push(v);
            }
        }
        return comps == 1;
    }

    // enumerate all sequences (only feasible for very small n,m)
    long long bruteforce_sumX_allseq() {
        const int P = n * (n + 1) / 2;
        vector<pair<int,int>> pairs;
        pairs.reserve(P);
        for (int u = 0; u < n; ++u) {
            for (int v = u; v < n; ++v) pairs.push_back({u, v});
        }

        long long ans = 0;

        function<void(int,long long,int)> dfs = [&](int step, long long X, int f_prev) {
            if (step == m) {
                ans = (ans + (X % MOD + MOD) % MOD) % MOD;
                return;
            }
            for (auto [u, v] : pairs) {
                // apply
                mult[u][v] += 1;
                if (u != v) mult[v][u] += 1;

                int f_now = bridge_count();
                if (f_now > f_prev) dfs(step + 1, X + A, f_now);
                else if (f_now == f_prev) dfs(step + 1, X + B, f_now);
                else dfs(step + 1, X + C, f_now);

                // undo
                mult[u][v] -= 1;
                if (u != v) mult[v][u] -= 1;
            }
        };

        int f0 = bridge_count(); // should be 0 at start
        dfs(0, 0, f0);
        return ans;
    }

    long long solve() {
        mult.assign(n, vector<int>(n, 0));

        // T=1：按题面直译，“好序列=开始时图是双连通(连通且 f(G)=0)”
        if (T == 1) {
            // 初始是 n 个孤点，n≥2 时不是连通图 => 好序列数为 0
            if (n >= 2) return 0;

            // n==1：连通且 f=0，所有序列都是好序列
            // 若 A=B=C：答案 = m*A * 1^m
            if (A == B && B == C) return ((m % MOD) * (A % MOD)) % MOD;

            // 其余 n==1 情况也能暴力（只有自环 1 种选择）
            long long X = 0;
            // 每步 f 都不会改变（始终为 0），X 加 B
            X = (m % MOD) * (B % MOD) % MOD;
            return X;
        }

        // T=2：所有序列
        // 特判 A==B==C：直接用公式
        if (A == B && B == C) {
            long long P = 1LL * n * (n + 1) / 2 % MOD;
            long long ways = modpow(P, m);
            long long per = (m % MOD) * (A % MOD) % MOD;
            return ways * per % MOD;
        }

        // 小数据直接暴力精确
        // 经验阈值：n,m <= 4 （P^m <= 10^4）
        if (n <= 4 && m <= 4) {
            return bruteforce_sumX_allseq();
        }

        // 超出已实现能力范围：保守返回 0（可继续扩展期望/DP以覆盖更大子任务）
        return 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver s;
    if (!(cin >> s.T >> s.n >> s.m >> s.A >> s.B >> s.C)) return 0;
    cout << s.solve() % MOD << "\n";
    return 0;
}

使用 & 说明

语言：C++17
取模：998244353
复杂度：
- 暴力部分： $O\!\left(\left(\frac{n(n+1)}{2}\right)^m \cdot (n+e)\right)$ ，仅用于 n,m 很小的子任务；
- 公式部分： $O(\log m)$ 。

可以继续扩展的方向（若你想再拿分）

当 $B=C$ 时， $X = m\cdot C + (A-C)\cdot \#(\text{使桥数增加的步数})$ 。
“桥数增加”只发生在连接不同连通块时，其次数 = “连通块数的减少量”。于是只需求随机过程执行 m 步后的期望连通块数并乘上总序列数，就能得出总和。这一块可以用“合并随机并查集”的概率 DP（跟踪两点同块概率）做出来。
对一般的 $A,B,C$ 再细分在同一连通块内且路径上含/不含桥的概率，需要跟踪双连通块结构；可用块树状态 DP（尺寸很大），或者做 n≤40 的 meet-in-the-middle/计数 DP。

如果你希望我把第 (1) 条也补上（B=C 的完整做法），告诉我参数范围，我直接把那条期望 DP 填进去。

Subtask分值𝑛,𝑚 𝑇 𝐴,𝐵,𝐶 1 12 ≤4 2 12 ≤8 3 12...

प्रश्न

Python

Python

Python

Python

Python

Python

Python

Python

विचार

Interpreting graph operations

Clarifying sequence conditions

Clarifying ambiguous start conditions

Interpreting the "good" operation sequence

Breaking down graph operations

Evaluating graph operations

Handling graph sequences

Analyzing component and edge dynamics

Discussion on randomness and component merging

Plan for small-case solution

Plan for partial solution

Final Plan for Code and Explanation

उत्तर

思路概要

代码（C++17，能直接提交）

使用 & 说明

可以继续扩展的方向（若你想再拿分）

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