分数: 300 点
问题陈述
你有 N 键已编号 1, 2, \dots, N.
其中一些是真正的钥匙,而另一些则是虚拟的。
有一个门,X 门,您可以在其中插入任意数量的钥匙。当且仅当至少 K 已插入真实钥匙。
您已进行 M 对这些键进行测试。的 i-th 测试如下:
- 您插入 C_i 键 A_{i,1}, A_{i,2}, \dots, A_{i,C_i} 进入X门。
- 测试结果由单个英文字母表示 R_i.
- R_i =
o表示 X 门在 i第次测试。 - R_i =
x表示 X 门在 i第次测试。
- R_i =
有 2^N 哪些键是真实的,哪些是虚拟的可能的组合。其中,找出与任何测试结果都不矛盾的组合数量。
给定的测试结果可能不正确,并且没有组合满足条件。遇到这种情况,请举报 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 \le N
- 1 \le A_{i,j} \le N
- A_{i,j} \neq A_{i,k} if j \neq k.
- R_i is
oorx.
输入
输入由标准输入按以下格式给出:
N M K
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1} R_1
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2} R_2
\vdots
C_M A_{M,1} A_{M,2} \dots A_{M,C_M} R_M
输出
将答案打印为整数。
示例输入 1
3 2 2 3 1 2 3 o 2 2 3 x
示例输出 1
2
在此输入中,有三个键并进行了两次测试。
需要两把正确的钥匙才能打开 X 门。
- 在第一个测试中,按键 使用 1, 2, 3 ,X门打开。
- 在第二个测试中,按键 使用了 2, 3 ,X门没有打开。
有两种组合,其中哪些键是真实的,哪些是虚拟的,与任何测试结果都不矛盾:
- 键 1 是真实的,关键 2 是一个假人,并且关键 3 是真实的。
- 键 1 是真实的,关键 2 是真实的,关键 3 是一个假人。
示例输入 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
正如问题陈述中提到的,答案可能是 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