Ta nhận thấy chỉ cần sinh các mã số thỏa mãn với một phản hồi của hệ thống, và kiểm tra xem nó có thỏa mãn mọi phản hồi không. Ta backtrack lưu lại trạng thái ~k~ là số vị trí giống của xâu ta đang xây dựng và xâu ~s_1~, thì ~k~ phải luôn nhỏ hơn hoặc bằng ~c_1~. Sau đó ta xét mọi phản hồi khác và kiểm tra nó có thỏa mãn không trong ~O(mn)~.

Số các mã số thỏa mãn một phản hồi ~c~ là ~C_n^c~. Độ phức tạp thuật toán là: ~O(mnC_n^5)~

Tuy nhiên ta có thể tối ưu về ~O(mC_n^5)~ bằng cách sử dụng bitmask.

Code mẫu:

#include{ <bits/stdc++.h>

using namespace std;

int M, N, result, C[11];
long long A[11];

void backtracking(int i, long long cur, int k) {
    if (i == N) {
        for (int i = 1; i <= M; ++i) 
            if (N - __builtin_popcountll(cur ^ A[i]) != C[i]) return;
        ++result;
        return;
    }
    backtracking(i + 1, cur ^ 1LL << i, k);
    if (k) backtracking(i + 1, cur, k - 1);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        string s; cin >> s >> C[i];
        for (int j = 0; j < N; ++j) if (s[j] == '1') A[i] ^= 1LL << j;
    }
    backtracking(0, A[1], C[1]);
    cout << result << '\n';
    return 0;
}