概要

各申告を「2 人のチーム番号の XOR が \(c\) である」という制約として考えます。
各操作後に、X を 0/1 に置き換える方法のうち、全体として矛盾しないものの個数を求めます。

考察

人 \(i\) の所属チームを \(t_i \in \{0,1\}\) とします。
申告 \((u,v,c)\) は次の制約になります。

\[ t_u \oplus t_v = c \]

• \(c=0\)：同じチーム
• \(c=1\)：異なるチーム

したがって、確定済みの申告だけを見ると、これは「XOR 制約の整合性判定」になります。
これは 重み付き Union-Find（Parity DSU） で判定できます。

---

一方で、X の申告をすべて試すと、X が \(x\) 個あるとき \(2^x\) 通りになり、到底間に合いません。
そこで、次の性質を使って数えます。

現在の申告全体について、

• \(G_{\text{all}}\)：X も含めた全申告を辺とするグラフ
• \(G_{\text{fix}}\)：内容が 0 または 1 の申告だけを辺とするグラフ

とします。

また、

\[ \operatorname{rank}(G) = N - \text{連結成分数} \]

とします。

まず、確定済み申告だけで矛盾しているなら、どのように X を埋めても良い確定方法は存在しないので答えは \(0\) です。

確定済み申告に矛盾がない場合、答えは

\[ 2^{\operatorname{rank}(G_{\text{all}}) - \operatorname{rank}(G_{\text{fix}})} \]

になります。

これは連結成分数で書くと、

\[ 2^{\text{連結成分数}(G_{\text{fix}}) - \text{連結成分数}(G_{\text{all}})} \]

です。

---

なぜこの式になるかを考えます。

確定済み申告だけを見たとき、各連結成分の中では、人同士の相対的なチーム関係はすでに決まっています。
ただし、その連結成分全体をチーム \(0/1\) 反転しても、申告の満たされ方は変わりません。

X の辺は、この確定済み成分同士をつなぐ辺だと考えられます。
\(G_{\text{all}}\) のある連結成分の中に、\(G_{\text{fix}}\) の連結成分が \(s\) 個含まれているとします。

この \(s\) 個それぞれについて反転するかどうかを選ぶと、X の値が決まります。
ただし、全体をまとめて反転してもすべての辺の XOR は変わらないため、異なる確定方法にはなりません。

したがって、この連結成分から得られる自由度は

\[ 2^{s-1} \]

です。

これをすべての \(G_{\text{all}}\) の連結成分について掛け合わせると、

\[ 2^{\text{連結成分数}(G_{\text{fix}}) - \text{連結成分数}(G_{\text{all}})} \]

となります。

例えば、3 頂点の三角形の 3 辺がすべて X の場合、良い確定方法はサイクル上の XOR が \(0\) になるものだけです。
このとき \(G_{\text{all}}\) の rank は \(2\)、\(G_{\text{fix}}\) の rank は \(0\) なので、答えは \(2^2=4\) 通りです。

アルゴリズム

各操作後に、現在存在する全申告を最初から見直して答えを計算します。
\(N,Q \leq 3000\) なので、毎回再計算しても十分間に合います。

各操作後の計算は次のように行います。

1. 通常の Union-Find all を用意する

   • X を含むすべての申告について、端点 \(u,v\) を連結する
   • これにより \(G_{\text{all}}\) の連結成分数が分かる

2. Parity DSU fixed を用意する

   • 内容が 0 または 1 の申告だけを追加する
   • 制約 \(t_u \oplus t_v = c\) に矛盾があるか判定する
   • 矛盾があれば答えは \(0\)

3. 矛盾がなければ、

\[ \operatorname{rank}_{\text{all}} = N - \text{all の連結成分数} \]

\[ \operatorname{rank}_{\text{fix}} = N - \text{fixed の連結成分数} \]

として、

\[ 2^{\operatorname{rank}_{\text{all}} - \operatorname{rank}_{\text{fix}}} \]

を出力する。

R k 操作では、申告 \(k\) の現在の内容を見て、それに \(1\) を加えたものを申告 \(k+1\) に上書きします。

• 0 → 1
• 1 → 0
• X → X

申告の内容は変化していくため、各申告の現在の内容を配列で管理します。

計算量

• 時間計算量: \(O(Q(N+Q)\alpha(N))\)
• 空間計算量: \(O(N+Q)\)

ここで \(\alpha(N)\) は Union-Find の逆 Ackermann 関数で、実質的には定数とみなせます。

実装のポイント

• 入力の人番号は \(1\) 始まりなので、実装では \(0\) 始まりに直します。

• R k では、\(k\) は \(1\) 始まりの申告番号です。

  • 申告 \(k\) は edges[k-1]
  • 申告 \(k+1\) は edges[k]

• Parity DSU では、各頂点について「親までの XOR」を持ちます。

  • find(x) は、根と「\(x\) から根までの XOR」を返します。
  • 同じ連結成分内に制約を追加するとき、既存の XOR と一致しなければ矛盾です。

• 多重辺があっても問題ありません。

  • 同じ 2 頂点間の複数申告も、Parity DSU が矛盾チェックとして正しく扱えます。

    ソースコード

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

static const long long MOD = 998244353;

struct Edge {
    int u, v;
    char c;
};

struct DSU {
    vector<int> p, sz;
    int comps;

    DSU(int n) : p(n), sz(n, 1), comps(n) {
        iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        comps--;
    }
};

struct ParityDSU {
    vector<int> p, sz, xr;
    int comps;

    ParityDSU(int n) : p(n), sz(n, 1), xr(n, 0), comps(n) {
        iota(p.begin(), p.end(), 0);
    }

    pair<int, int> find(int x) {
        if (p[x] == x) return {x, 0};
        auto [r, v] = find(p[x]);
        xr[x] ^= v;
        p[x] = r;
        return {p[x], xr[x]};
    }

    bool unite(int a, int b, int w) {
        auto [ra, xa] = find(a);
        auto [rb, xb] = find(b);

        if (ra == rb) {
            return ((xa ^ xb) == w);
        }

        if (sz[ra] < sz[rb]) {
            swap(ra, rb);
            swap(xa, xb);
        }

        p[rb] = ra;
        xr[rb] = xa ^ xb ^ w;
        sz[ra] += sz[rb];
        comps--;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<long long> pow2(N + Q + 10, 1);
    for (int i = 1; i < (int)pow2.size(); i++) {
        pow2[i] = pow2[i - 1] * 2 % MOD;
    }

    vector<Edge> edges;

    auto calc = [&]() -> long long {
        DSU all(N);
        ParityDSU fixed(N);
        bool ok = true;

        for (const auto &e : edges) {
            all.unite(e.u, e.v);

            if (e.c != 'X') {
                int w = e.c - '0';
                if (!fixed.unite(e.u, e.v, w)) {
                    ok = false;
                }
            }
        }

        if (!ok) return 0;

        int rank_all = N - all.comps;
        int rank_fixed = N - fixed.comps;
        return pow2[rank_all - rank_fixed];
    };

    for (int qi = 0; qi < Q; qi++) {
        string op;
        cin >> op;

        if (op == "A") {
            int u, v;
            char c;
            cin >> u >> v >> c;
            --u;
            --v;
            edges.push_back({u, v, c});
        } else {
            int k;
            cin >> k;
            char c = edges[k - 1].c;
            if (c == '0') c = '1';
            else if (c == '1') c = '0';
            edges[k].c = c;
        }

        cout << calc() << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。