各クエリについて、ありうる \(N!\) 通りの操作列のうち、点灯しているランプの途中経過の個数の列が \(C_i\) となるものの個数を求める問題です。

初めに \(N!\) 通りの全てのありうる操作列を全探索し、それぞれについて有効な操作列であるかを判定します。有効な場合は、今回の問題を解くに当たって重要である点灯しているランプの個数の途中経過を記録した配列を保存します。具体的には配列をキーに取る連想配列を用意し、記録した配列をキーとする要素に \(1\) 加算します。

判定は問題文にある通りに愚直にしても計算量 \(\mathrm{O}(NK)\) であり、全探索すると時間計算量 \(\mathrm{O}(NK \times N! )\) となります。また、各クエリを答えるときは連想配列を参照するだけでであるため、全体で時間計算量 \(\mathrm{O}(NK \times N! +QN)\) などで解くことができて、今回の制約では実行時間制限に十分間に合います。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k, q;
    cin >> n >> k >> q;
    string s;
    cin >> s;
    vector<int> c(n);
    for (auto& e : c) cin >> e;
    vector<string> a(n), b(n), x(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> x[i];
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    map<vector<int>, int> mp;
    do {
        string now = s;
        bool flag = true;
        vector<int> tmp;
        for (int i = 0; i < n; ++i) {
            bool f = true;
            for (int j = 0; j < k; ++j) {
                if (a[p[i]][j] == '1' && now[j] != '1') f = false;
                if (b[p[i]][j] == '1' && now[j] != '0') f = false;
            }
            if (!f) {
                flag = false;
                break;
            }
            for (int j = 0; j < k; ++j)
                if (x[p[i]][j] == '1') now[j] ^= 1;
            int cnt = 0;
            for (auto e : now)
                if (e == '1') cnt++;
            tmp.push_back(cnt);
        }
        if (flag) mp[tmp]++;
    } while (next_permutation(p.begin(), p.end()));
    for (int i = 0; i < q; ++i) {
        int t, y;
        cin >> t >> y;
        t--;
        c[t] = y;
        cout << mp[c] << endl;
    }
}