← 返回题目列表

AtCoder · abc356_c

E. 按键

中文机器翻译题面 查看原题

分数: 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第次测试。

有 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 o or x.

输入

输入由标准输入按以下格式给出:

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