题目详情
返回题库题目描述
您有N把钥匙，编号为1,2,…,N。
其中一些是真钥匙，其他的是假钥匙。
有一扇门，门 X，你可以插入任意数量的钥匙。只有插入至少K把真钥匙，X 门才会打开。
你已经对这些钥匙进行了M次测试。第i次测试过程如下：
- 您将Ci（$A_{i,1},A_{i,2}......A_{i,Ci}$）把钥匙插入了 X 号门。
- 测试结果用一个英文字母Ri表示。
- Ri=o表示在第i次测试中门 X 打开了。
- Ri=x 表示在第i次试中，门X没有打开。
有$2^N$种可能的钥匙组合，其中哪些是真钥匙，哪些是假钥匙。在这些组合中，找出与任何测试结果都不矛盾的组合数。
给定的测试结果有可能是错误的，没有任何组合满足条件。在这种情况下，报告0。
输入描述
第一行钥匙数量N，M次测试，K
接下来M行，分别输入第i测试的钥匙数量，以及$C_i$把钥匙的编号$A_{ij}$，最后是$R_i$代表门是否打开
数据范围：
- 1≤K≤N≤15
- 1≤M≤100
- 1≤$C_i$≤N
- 1≤$A_{i,j}$≤N
- $A_{ij}$≠$A_{ik}$,if ≠.
- $R_i$为
o或x.
输出描述
输出一个整数代表答案
提示
样例1：
在此输入中，有三个键，进行了两次测试。
打开 X 门需要两把正确的钥匙。
- 在第一次测试中，使用了钥匙1,2,3，X 门打开了。
- 在第二次测试中，使用了钥匙2,3，X 门没有打开。
有两种组合，哪把钥匙是真钥匙，哪把钥匙是假钥匙，这两种组合与任何测试结果都没有矛盾：
- 钥匙1是真的，钥匙2是假的，钥匙3是真的。
- 密钥1是真实的，密钥2是真实的，密钥3是假的。