Overview

Since \(N \leq 9\) is small, we can enumerate all possible execution orders of the operations.
For each execution order, we precompute the “sequence of lit lamp counts after each day” and then quickly answer how many orders match the corrected record.

Analysis

The order of operations is a permutation of \(N\) operation indices, so there are at most

\[ 9! = 362880 \]

possibilities. This is small enough to enumerate.

On the other hand, the number of corrections is large, with \(Q \leq 10^5\).
If we try all permutations for each correction, the complexity becomes

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

which is too slow.

Instead, we think as follows.

When we fix an operation order, by executing the operations sequentially from the initial state \(S\):

• Whether that order is feasible
• If feasible, what the sequence of lit lamp counts after each day is

are uniquely determined.

In other words, if we precompute for all orders

lit count sequence \(\rightarrow\) number of execution orders that produce that sequence

then for each query, we simply look up the lit count sequence of the current record and retrieve its count.

Since the number of lit lamps is between \(0\) and \(K\), we can encode a lit count sequence of length \(N\) as an integer in base \(K+1\).

For example, when \(K=3\), if the lit count sequence is

\[ (2, 0, 3) \]

then using base \(K+1=4\), it can be represented as

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

Since each digit is between \(0\) and \(K\), representing it in base \(K+1\) ensures no collisions and unique management.

Algorithm

First, convert the lamp states and conditions, represented as 0/1 strings, into integers as bit strings.

• If lamp \(j\) is lit, set that bit to \(1\)
• If lamp \(j\) is off, set that bit to \(0\)

Whether operation \(i\) is executable in the current state state can be determined as follows:

• All bits that are 1 in \(A_i\) must also be 1 in state
• All bits that are 1 in \(B_i\) must be 0 in state

Therefore, the conditions are

\[ (state \mathbin{\&} A_i) = A_i \]

and

\[ (state \mathbin{\&} B_i) = 0 \]

If executable, the state after the operation is computed as

\[ state \leftarrow state \oplus X_i \]

This is because only the positions where \(X_i\) has bit \(1\) are toggled.

The procedure is as follows:

1. Set the base as \(base = K+1\).
2. Precompute \(base^0, base^1, \ldots, base^{N-1}\).
3. Enumerate all permutations of the operation indices.
4. For each permutation, simulate the operations sequentially from the initial state.
   • If any operation’s execution condition is not satisfied, the permutation is invalid.
   • If all operations execute successfully, construct the lit count sequence after each day.
5. Encode the lit count sequence as a base-\(base\) integer and increment freq[code] by \(1\).
6. Encode the current record \(C\) in the same way.
7. For each correction:
   • Update current_code by reflecting only the changed value on day \(T\).
   • Output freq[current_code].

For updates due to corrections, since only the value on day \(T\) changes from \(C_T\) to \(Y\):

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

allows for fast updates.

Complexity

• Time complexity: \(O(N! \cdot N + Q)\)
• Space complexity: \(O(N!)\)

Implementation Notes

• Since \(K \leq 9\), the lamp state can be sufficiently represented as a bit string of an integer.

• The number of lit lamps can be efficiently counted using __builtin_popcount.

• Base \(K+1\) is used for encoding the lit count sequence.

  • Since each lit count is between \(0\) and \(K\), it can be safely treated as a digit.

• Even if operations have the same conditions and effects, if their operation indices differ, they must be counted as different orders.

  • Therefore, simply enumerating permutations of operation indices gives the correct count.

• If the same position in \(A_i\) and \(B_i\) is both 1, that operation cannot be executed in any state.

  • The bit-based condition check naturally determines this as impossible.

    Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.