枚举2^15种情况判断是否成立
注意 这里枚举的是"每把钥匙是否是正确的钥匙" 判断是否是正确的
O((2^n)*m)
code:
#include <bits/stdc++.h>
using namespace std;
int a[105], b[105];
char isg[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1;i <= m;i++){
        int c;
        cin >> c;
        while(c--){
            int x;
            cin >> x;
            a[i] |= 1 << x - 1;
        }
        cin >> isg[i];
    }

    int ans = 0;
    for(int i = 0;i <= (1 << n) - 1;i++){
        int ok = 1;
        for(int j = 1;j <= m;j++){
            bool t = __builtin_popcount(i & a[j]) >= k; 
            if(t && isg[j] == 'x' || !t && isg[j] == 'o')ok = 0;
        }
        ans += ok;
    }

    cout << ans << endl;
    return 0;
}