概要

\(N \leq 9\) と小さいため、操作の実行順序をすべて列挙できます。
各実行順序について「各日終了後の点灯数列」を求めておき、訂正後の記録と一致する順序数を高速に答えます。

考察

操作の順序は \(N\) 個の操作番号の順列なので、最大でも

\[ 9! = 362880 \]

通りです。これは十分列挙可能です。

一方で、訂正回数は \(Q \leq 10^5\) と大きいです。
各訂正ごとに全順列を試すと、

\[ O(Q \cdot N! \cdot N) \]

となり、間に合いません。

そこで、次のように考えます。

ある操作順序を固定すると、初期状態 \(S\) から順に操作を実行していくことで、

• その順序が実行可能か
• 実行可能なら、各日終了後の点灯数列が何になるか

が一意に決まります。

つまり、すべての順序についてあらかじめ

点灯数列 \(\rightarrow\) その点灯数列を作る実行順序の個数

を数えておけば、各クエリでは現在の記録の点灯数列を見て、その個数を取り出すだけで済みます。

点灯数は \(0\) 以上 \(K\) 以下なので、長さ \(N\) の点灯数列を \(K+1\) 進数の整数としてエンコードできます。

例えば \(K=3\) のとき、点灯数列が

\[ (2, 0, 3) \]

なら、基数を \(K+1=4\) として

\[ 2 + 0 \cdot 4 + 3 \cdot 4^2 \]

のように表せます。

各桁が \(0\) 以上 \(K\) 以下なので、\(K+1\) 進数で表せば衝突せず一意に管理できます。

アルゴリズム

まず、0/1 文字列で表されたランプ状態や条件をビット列として整数に変換します。

• ランプ \(j\) が点灯しているなら、そのビットを \(1\)
• 消灯しているなら、そのビットを \(0\)

として扱います。

操作 \(i\) が現在の状態 state で実行可能かは、次で判定できます。

• \(A_i\) で 1 のビットは、すべて state でも 1 である必要がある
• \(B_i\) で 1 のビットは、すべて state では 0 である必要がある

よって条件は

\[ (state \& A_i) = A_i \]

かつ

\[ (state \& B_i) = 0 \]

です。

実行可能なら、操作後の状態は

\[ state \leftarrow state \oplus X_i \]

で求められます。

これは、\(X_i\) のビットが \(1\) の場所だけ反転するためです。

手順は次の通りです。

1. 基数を \(base = K+1\) とする。
2. \(base^0, base^1, \ldots, base^{N-1}\) を前計算する。
3. 操作番号の全順列を列挙する。
4. 各順列について、初期状態から順に操作をシミュレーションする。
   • 実行条件を満たさない操作があれば、その順列は無効。
   • 最後まで実行できたら、各日終了後の点灯数列を作る。
5. 点灯数列を \(base\) 進数として整数にエンコードし、freq[code] を \(1\) 増やす。
6. 現在の記録 \(C\) も同様にエンコードしておく。
7. 各訂正について、
   • 変更された日 \(T\) の値だけを反映して current_code を更新する。
   • freq[current_code] を出力する。

訂正による更新は、\(T\) 日目の値が \(C_T\) から \(Y\) に変わるだけなので、

\[ current\_code \mathrel{+}= (Y - C_T) \cdot base^{T-1} \]

で高速に更新できます。

計算量

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

実装のポイント

• \(K \leq 9\) なので、ランプ状態は整数のビット列で十分表せます。

• 点灯数は __builtin_popcount で高速に数えられます。

• 点灯数列のエンコードには \(K+1\) 進数を使います。

  • 各点灯数は \(0\) 以上 \(K\) 以下なので、桁として安全に扱えます。

• 同じ条件・効果を持つ操作があっても、操作番号が異なれば別の順序として数える必要があります。

  • そのため、操作番号の順列をそのまま列挙すれば正しく数えられます。

• \(A_i\) と \(B_i\) の同じ位置が両方 1 の場合、その操作はどの状態でも実行できません。

  • ビット判定式により自然に不可能と判定されます。

    ソースコード

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

static const long long MOD = 998244353;

int to_mask(const string& s) {
    int m = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '1') m |= (1 << i);
    }
    return m;
}

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

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

    string S;
    cin >> S;
    int init = to_mask(S);

    vector<int> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];

    vector<int> A(N), B(N), X(N);
    for (int i = 0; i < N; i++) {
        string a, b, x;
        cin >> a >> b >> x;
        A[i] = to_mask(a);
        B[i] = to_mask(b);
        X[i] = to_mask(x);
    }

    int base = K + 1;
    vector<int> pow_base(N);
    pow_base[0] = 1;
    for (int i = 1; i < N; i++) pow_base[i] = pow_base[i - 1] * base;

    unordered_map<int, long long> freq;

    vector<int> p(N);
    iota(p.begin(), p.end(), 0);

    do {
        int state = init;
        int code = 0;
        bool ok = true;

        for (int t = 0; t < N; t++) {
            int op = p[t];

            if ((state & A[op]) != A[op] || (state & B[op]) != 0) {
                ok = false;
                break;
            }

            state ^= X[op];
            int cnt = __builtin_popcount((unsigned)state);
            code += cnt * pow_base[t];
        }

        if (ok) {
            freq[code]++;
            if (freq[code] >= MOD) freq[code] %= MOD;
        }
    } while (next_permutation(p.begin(), p.end()));

    int current_code = 0;
    for (int i = 0; i < N; i++) {
        current_code += C[i] * pow_base[i];
    }

    for (int q = 0; q < Q; q++) {
        int T, Y;
        cin >> T >> Y;
        --T;

        current_code += (Y - C[T]) * pow_base[T];
        C[T] = Y;

        auto it = freq.find(current_code);
        cout << (it == freq.end() ? 0LL : it->second % MOD) << '\n';
    }

    return 0;
}

---

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