Keys

题目描述

你有编号为 $1, 2, \dots, N$ 的 $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}$ $\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$

输出格式

输出一个整数，表示答案。

3 2 2
3 1 2 3 o
2 2 3 x

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

0

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

8

提示

$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$ 若 $j \neq k$ 则 $A_{i,j} \neq A_{i,k}$。 $R_i$ 为 $o$ 或 $x$。在此输入中，有三把钥匙并进行了两次测试。
需要两把正确的钥匙才能打开门 X。

在第一次测试中，使用了钥匙 $1, 2, 3$，门 X 打开了。 在第二次测试中，使用了钥匙 $2, 3$，门 X 没有打开。

存在两种不与任何测试结果矛盾的钥匙真假组合：

钥匙 $1$ 为真，钥匙 $2$ 为假，钥匙 $3$ 为真。 钥匙 $1$ 为真，钥匙 $2$ 为真，钥匙 $3$ 为假。
如问题描述中所述，答案可能为 $0$.

标签: AtCoder|abc356C

来源

AtCoder|abc356C