概要

\(N\) 人の人々を 2 つのチームに分ける際、与えられた「同じチームであるべき」「異なるチームであるべき」という制約（申告）を矛盾なく満たす方法が何通りあるかを求める問題です。一部の制約が未確定（X）であるため、それらを 0 または 1 に確定させる方法のうち、矛盾が生じないものの個数を数え上げます。

考察

1. グラフ問題への言い換え

この問題は、各人を頂点、申告を辺とするグラフとして考えることができます。 - 内容 0（同じチーム）：頂点 \(u, v\) は同じ色であるべき。 - 内容 1（異なるチーム）：頂点 \(u, v\) は異なる色であるべき。 - 内容 X（未確定）：0 か 1 のどちらかを割り当てる。

これは、各頂点 \(i\) に変数 \(x_i \in \{0, 1\}\)（所属チーム）を割り当て、辺 \((u, v)\) に対して \(x_u \oplus x_v = c\) という制約を課していると解釈できます（\(\oplus\) は XOR）。

2. 矛盾なく確定できる条件

ある確定方法が「良い確定方法」であるためには、全ての制約 \(x_u \oplus x_v = c\) を同時に満たす \(x_1, \ldots, x_N\) が存在する必要があります。 グラフ理論的には、「どのサイクルにおいても、そのサイクルに含まれる辺の重み \(c\) の XOR 総和が \(0\) であること」が条件です。特に、c=1 の辺のみを考えた場合に「奇サイクルが存在しない（二部グラフである）」という性質の一般化と言えます。

3. 良い確定方法の数え上げ

現在の申告によって作られるグラフにおいて、以下の 2 つの状態を考えます。 - グラフ \(G_{all}\): 全ての申告（0, 1, X）を辺としたグラフ。 - グラフ \(G_{fixed}\): すでに内容が 0 または 1 に確定している申告のみを辺としたグラフ。

まず、\(G_{fixed}\) 自体に矛盾がある（例：ある 2 人が同じチームであるべきかつ異なるチームであるべきと導かれる）場合、答えは \(0\) 通りです。

矛盾がない場合、未確定の辺 X をどう決めるかを考えます。 1. \(u, v\) が \(G_{fixed}\) で既に同じ連結成分に属している場合： \(x_u \oplus x_v\) の値は一意に決まっています。したがって、辺 X の値は、矛盾を起こさないための \(1\) 通りに固定されます。 2. \(u, v\) が \(G_{fixed}\) で異なる連結成分に属している場合： 辺 X の値を 0 にしても 1 にしても矛盾は生じません。この辺を追加することで、2 つの連結成分が 1 つに統合されます。このとき、自由度が 1 つ減り、選択肢が \(2\) 倍になります。

これを一般化すると、良い確定方法の個数は以下の式で求められます。 $\(\text{個数} = 2^{(\text{\)G{fixed}\( の連結成分数}) - (\text{\)G{all}\( の連結成分数})}\)\( ※ 各 `X` の辺が \)G_{fixed}\( の異なる連結成分を繋ぐたびに、その値を \)0, 1$ どちらにするかの選択肢（2通り）が生まれるためです。

4. クエリへの対応

\(N, Q \leq 3000\) と制約が小さいため、各クエリごとにグラフを再構築しても間に合います。 - A 操作：申告リストに新しい制約を追加し、\(G_{all}\) の連結成分数を更新します。 - R 操作：指定された申告の内容を書き換えます。 - 毎ステップ：\(G_{fixed}\) を一から構築し直し、矛盾の有無と連結成分数を数えます。

アルゴリズム

1. 準備:
   • 申告を保存するリストを持つ。
   • \(G_{all}\) の連結成分数を管理するための Union-Find（DSU）を用意する。
2. 各クエリの処理:
   • A 操作ならリストに追加し、\(G_{all}\) 用の DSU を更新。
   • R 操作ならリスト内の内容を書き換え。
   • 判定:
     • 新しい DSU（\(G_{fixed}\) 用）を作成。
     • 重み付き DSU を用いて、0 と 1 の制約を順に unite していく。
     • unite 中に \(x_u \oplus x_v \neq c\) となる矛盾が発生したら、答えは \(0\)。
     • 矛盾がなければ、\(2^{(G_{fixed} \text{の成分数} - G_{all} \text{の成分数})} \pmod{998244353}\) を出力。

計算量

• 時間計算量: \(O(Q \cdot (N + Q \alpha(N)))\)
  • 各クエリにおいて、最大 \(Q\) 本の辺を DSU に追加します。
  • 全体で \(Q^2\) 程度の操作回数となり、\(3000^2 = 9 \times 10^6\) なので、制限時間内に十分収まります。
• 空間計算量: \(O(N + Q)\)
  • 申告の保存と DSU の管理に利用します。

実装のポイント

• 重み付き DSU: 根からの XOR 距離（\(x_{root} \oplus x_i\)）を保持することで、任意の 2 頂点間の \(x_u \oplus x_v\) の値を \(O(\alpha(N))\) で判定できます。

• 連結成分数の管理: DSU の unite 操作が成功する（異なる成分が繋がる）たびに、成分数を \(1\) 減らすことで簡単に管理できます。

• R 操作の伝搬: 申告 \(k\) が X のとき、申告 \(k+1\) も X になるというルールに注意してください。コードでは add_one 関数でこれを処理しています。”`python char add_one(char c) { if (c == ‘X’) return ‘X’; if (c == ‘0’) return ‘1’; return ‘0’; }

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// Precompute powers of 2 modulo 998244353
long long power2[3005];
const int MOD = 998244353;

// DSU structure that maintains XOR distances to check consistency and count components
struct DSU {
    vector<int> parent;
    vector<int> dist; // dist[i] is the XOR distance from i to parent[i]
    int components;
    bool inconsistent;

    DSU(int n) : parent(n + 1), dist(n + 1, 0), components(n), inconsistent(false) {
        iota(parent.begin(), parent.end(), 0);
    }

    // Reset the DSU to its initial state for each query
    void reset(int n) {
        iota(parent.begin(), parent.begin() + n + 1, 0);
        fill(dist.begin(), dist.begin() + n + 1, 0);
        components = n;
        inconsistent = false;
    }

    // Standard DSU find with path compression and distance update
    pair<int, int> find(int i) {
        if (parent[i] == i)
            return {i, 0};
        pair<int, int> root = find(parent[i]);
        parent[i] = root.first;
        dist[i] = dist[i] ^ root.second;
        return {parent[i], dist[i]};
    }

    // Standard DSU unite with XOR distance constraint
    void unite(int i, int j, int d) {
        if (inconsistent) return;
        pair<int, int> root_i = find(i);
        pair<int, int> root_j = find(j);
        if (root_i.first != root_j.first) {
            parent[root_i.first] = root_j.first;
            // s_i ^ s_j = d, s_i ^ s_root_i = root_i.second, s_j ^ s_root_j = root_j.second
            // s_root_i ^ s_root_j = (s_root_i ^ s_i) ^ (s_i ^ s_j) ^ (s_j ^ s_root_j)
            // s_root_i ^ s_root_j = root_i.second ^ d ^ root_j.second
            dist[root_i.first] = root_i.second ^ d ^ root_j.second;
            components--;
        } else {
            // If already in the same component, the existing distance must match the new constraint
            if ((root_i.second ^ root_j.second) != d) {
                inconsistent = true;
            }
        }
    }
};

// Simple DSU to maintain components of all declarations (G_all)
struct SimpleDSU {
    vector<int> parent;
    int components;

    SimpleDSU(int n) : parent(n + 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
};

// Declaration record
struct Decl {
    int u, v;
    char c;
};

// Logic for the R k operation (X + 1 = X, 0 + 1 = 1, 1 + 1 = 0)
char add_one(char c) {
    if (c == 'X') return 'X';
    if (c == '0') return '1';
    return '0';
}

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Precompute powers of 2
    power2[0] = 1;
    for (int i = 1; i <= N; ++i) {
        power2[i] = (power2[i - 1] * 2) % MOD;
    }

    vector<Decl> decls;
    SimpleDSU dsu_all(N); // To maintain components in the graph with all current declarations
    DSU dsu_fixed(N);     // To maintain components and check consistency of c=0,1 declarations

    for (int i = 0; i < Q; ++i) {
        char type;
        cin >> type;
        if (type == 'A') {
            int u, v;
            char c;
            cin >> u >> v >> c;
            decls.push_back({u, v, c});
            dsu_all.unite(u, v);
        } else if (type == 'R') {
            int k;
            cin >> k;
            // R k updates declaration k+1 (index k in 0-indexed vector)
            decls[k].c = add_one(decls[k - 1].c);
        }

        // Re-evaluate consistency and find components for fixed declarations
        dsu_fixed.reset(N);
        for (const auto& d : decls) {
            if (d.c != 'X') {
                dsu_fixed.unite(d.u, d.v, d.c - '0');
                if (dsu_fixed.inconsistent) break;
            }
        }

        if (dsu_fixed.inconsistent) {
            cout << "0\n";
        } else {
            // The number of good determinations is 2^(C_fixed - C_all)
            int diff = dsu_fixed.components - dsu_all.components;
            cout << power2[diff] << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。