概要

\(N\) 種類の操作を \(N\) 日間ですべて 1 回ずつ行うとき、与えられた「各操作後の点灯ランプ数」の記録と矛盾しない操作順序（順列）の個数を求める問題です。記録には \(Q\) 回の値の変更（訂正）が入るため、各訂正ごとに素早く回答する必要があります。

考察

1. 制約に着目する

この問題で最も重要なのは、\(N \leq 9\) および \(K \leq 9\) という非常に小さな制約です。 \(N\) 種類の操作の並べ替え（順列）の総数は \(N!\) 通りであり、\(N=9\) のとき \(9! = 362,880\) です。この程度の数であれば、すべての順列についてシミュレーションを行うことが可能です。

2. クエリへの対応

記録の訂正クエリが \(Q = 10^5\) 回と多いため、クエリごとに全順列を調べ直すと間に合いません。 しかし、操作の内容（条件 \(A_i, B_i\) や効果 \(X_i\)）は固定されています。したがって、「どの順列がどのような点灯個数の推移を生むか」を事前に計算しておくことができます。

各順列において、途中で実行条件を満たせなくなる場合は無視し、最後まで実行できる場合はそのときの点灯個数の推移 \((c_1, c_2, \dots, c_N)\) を記録します。この推移をキー、その推移が発生する順列の個数を値としたハッシュマップ（連想配列）を作成すれば、クエリに対して高速に応答できます。

3. 推移のハッシュ化

点灯個数の推移 \((c_1, c_2, \dots, c_N)\) をハッシュマップのキーにする際、配列のまま扱うよりも 1 つの整数にまとめる（ハッシュ化する）と効率的です。 各日の点灯個数 \(C_t\) は \(0\) 以上 \(K=9\) 以下なので、11進法と見なして計算することで、一意な整数として表現できます。 $\(\text{key} = \sum_{t=1}^{N} C_t \times 11^{t-1}\)$

アルゴリズム

1. 事前計算（全順列の探索）:

   • \(N!\) 通りの操作順列を next_permutation 等で生成します。
   • 各順列について、初期状態 \(S\) からシミュレーションを行います。
     • 操作の実行条件（\(A_i\) のビットが立っているか、\(B_i\) のビットが寝ているか）をビット演算で判定します。
     • 条件を満たせば \(X_i\) で反転（XOR）させ、現在の点灯個数（popcount）を記録します。
   • 無事に \(N\) 回の操作を終えたら、その点灯個数の推移を11進法の数値に変換し、ハッシュマップ sequence_counts のカウントを増やします。

2. クエリ処理:

   • 現在の記録 \(C_1, \dots, C_N\) に対応する11進法の値を保持しておきます。
   • 訂正 \(T_q, Y_q\) が来たら、保持している値を差分更新し、新しい記録に対応するハッシュ値を計算します。
   • ハッシュマップからその値に対応する順列の個数を取り出して出力します。

計算量

• 事前計算: \(O(N! \cdot N)\)
  • \(9! \times 9 \approx 3.3 \times 10^6\) 回のループで、十分高速です。
• クエリ処理: \(O(Q)\)
  • 各クエリ \(O(1)\) でハッシュマップを参照します。
• 空間計算量: \(O(N!)\)
  • ハッシュマップに最大 \(N!\) 個の要素が格納されます。

実装のポイント

• ビット演算: ランプの状態や操作条件は \(K \leq 9\) なので、整数型のビットフラグで管理すると高速です。

  • 条件チェック: (state & A[i]) == A[i] && (state & B[i]) == 0
  • 状態更新: state ^= X[i]

• ハッシュマップの最適化: C++ の std::unordered_map を使用する場合、アンチハッシュ（最悪ケース）を避けるためにカスタムハッシュ関数を使用するとより安全です。

• popcount: 点灯しているランプの個数を数えるには、C++20 の std::popcount や __builtin_popcount が便利です。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <chrono>
#include <bit>

using namespace std;

/**
 * Custom hash for unordered_map to improve performance and avoid anti-hash test cases.
 * This uses a steady clock and a splitmix64 algorithm for good distribution.
 */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    // Standard competitive programming optimizations for faster I/O.
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // Initial panel state S.
    string S_str;
    cin >> S_str;
    unsigned int S = 0;
    for (int i = 0; i < K; ++i) {
        if (S_str[i] == '1') S |= (1u << i);
    }

    // Records of the number of lamps lit after each day's operation.
    vector<int> C(N);
    for (int i = 0; i < N; ++i) cin >> C[i];

    // Conditions and effects for each operation.
    vector<unsigned int> A(N, 0), B(N, 0), X(N, 0);
    for (int i = 0; i < N; ++i) {
        string a_s, b_s, x_s;
        cin >> a_s >> b_s >> x_s;
        for (int j = 0; j < K; ++j) {
            if (a_s[j] == '1') A[i] |= (1u << j);
            if (b_s[j] == '1') B[i] |= (1u << j);
            if (x_s[j] == '1') X[i] |= (1u << j);
        }
    }

    /**
     * Precompute powers of 11 to represent the sequence (C_1, C_2, ..., C_N)
     * as a unique long long value. Since C_t <= K <= 9, base 11 is sufficient.
     */
    long long powers[10];
    powers[0] = 1;
    for (int i = 1; i < 10; ++i) powers[i] = powers[i - 1] * 11;

    /**
     * Iterate through all N! permutations of operations.
     * For each permutation, check if it's valid according to conditions A_i, B_i.
     * If valid, calculate the resulting sequence of lamp counts (c_1, ..., c_N)
     * and store its frequency in a hash map.
     */
    unordered_map<long long, int, custom_hash> sequence_counts;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) p[i] = i;

    do {
        unsigned int current_mask = S;
        long long seq_val = 0;
        bool valid = true;
        for (int i = 0; i < N; ++i) {
            int op = p[i];
            // Condition check: bits in A_i must be 1, bits in B_i must be 0.
            if ((current_mask & A[op]) == A[op] && (current_mask & B[op]) == 0) {
                current_mask ^= X[op];
                int cnt = std::popcount(current_mask);
                seq_val += (long long)cnt * powers[i];
            } else {
                valid = false;
                break;
            }
        }
        if (valid) {
            sequence_counts[seq_val]++;
        }
    } while (next_permutation(p.begin(), p.end()));

    // Calculate the sequence value for the current record C.
    long long current_seq_val = 0;
    for (int i = 0; i < N; ++i) {
        current_seq_val += (long long)C[i] * powers[i];
    }

    /**
     * Process Q corrections. Each correction updates one day's recorded count.
     * We update the current_seq_val incrementally and lookup the precomputed count.
     */
    for (int q = 0; q < Q; ++q) {
        int T, Y;
        cin >> T >> Y;
        // Update C[T-1] to Y and update current_seq_val accordingly.
        current_seq_val -= (long long)C[T - 1] * powers[T - 1];
        C[T - 1] = Y;
        current_seq_val += (long long)C[T - 1] * powers[T - 1];

        // Retrieve the number of permutations that result in the current sequence.
        auto it = sequence_counts.find(current_seq_val);
        if (it != sequence_counts.end()) {
            // N! <= 362,880, so it fits within the modulo 998244353.
            cout << it->second << "\n";
        } else {
            cout << 0 << "\n";
        }
    }

    return 0;
}

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