4192: Keys

# Keys ### 内存 1024MB ### 时间 2S ## 题目描述 小高有 $N$ 把钥匙，编号从 $1$ 到 $N$。其中一些是真钥匙，其他是假钥匙。有一扇门X，你可以往里插入任意数量的钥匙。只有当至少插入 $K$ 把真钥匙时，门X才会打开。小高进行了 $M$ 次测试。第 $i$ 次测试如下： - 他往门X里插入了 $C_i$ 把钥匙 $A_{i,1}, A_{i,2}, \dots, A_{i,C_i}$。 - 测试结果用一个英文字母 $R_i$ 表示。 - $R_i = $ `o` 表示在第 $i$ 次测试中门X打开了。 - $R_i = $ `x` 表示在第 $i$ 次测试中门X没有打开。 一共有 $2^N$ 种可能的真假钥匙组合。在这些组合中，找出不与任何测试结果矛盾的组合数量。如果给定的测试结果不正确，没有任何组合满足条件，则输出 $0$。 ## 输入格式 输入按以下格式从标准输入给出： $N$ $M$ $K$ $C_1$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,C_1}$ $R_1$ $C_2$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,C_2}$ $R_2$ $\vdots$ $C_M$ $A_{M,1}$ $A_{M,2}$ $\cdots$ $A_{M,C_M}$ $R_M$ ## 输出格式 将答案作为一个整数输出。 ## 输入输出样例 ### 输入样例1 ``` 3 2 2 3 1 2 3 o 2 2 3 x ``` ### 输出样例1 ``` 2 ``` ### 输入样例2 ``` 4 5 3 3 1 2 3 o 3 2 3 4 o 3 3 4 1 o 3 4 1 2 o 4 1 2 3 4 x ``` ### 输出样例2 ``` 0 ``` ### 输入样例3 ``` 11 4 9 10 1 2 3 4 5 6 7 8 9 10 o 11 1 2 3 4 5 6 7 8 9 10 11 o 10 11 10 9 8 7 6 5 4 3 2 x 10 11 9 1 4 3 7 5 6 2 10 x ``` ### 输出样例3 ``` 8 ``` ## 数据范围与提示 【样例说明1】 在这个输入中，有三把钥匙，进行了两次测试。 需要两把正确的钥匙才能打开门X。 - 在第一次测试中，使用了钥匙 $1, 2, 3$，门X打开了。 - 在第二次测试中，使用了钥匙 $2, 3$，门X没有打开。 有两种真假钥匙组合不与任何测试结果矛盾： - 钥匙 $1$ 是真的，钥匙 $2$ 是假的，钥匙 $3$ 是真的。 - 钥匙 $1$ 是真的，钥匙 $2$ 是真的，钥匙 $3$ 是假的。 【样例说明2】 如题目陈述所说，答案可能是 $0$。 【数据范围】 - $N$, $M$, $K$, $C_i$, 和 $A_{i,j}$ 都是整数。 - $1 \le K \le N \le 15$ - $1 \le M \le 100$ - $1 \le C_i,A_{i,j} \le N$ - 如果 $j \neq k$ 则 $A_{i,j} \neq A_{i,k}$ - $R_i$ 是 `o` 或 `x`。 ## 题目来源 ABC356C