#ABC356C. 钥匙谜题
钥匙谜题
AT_abc356_c [ABC356C] Keys
题目描述
你有 把编号为 的钥匙,其中一些是真钥匙,其余都是假钥匙。
有一扇 X 门,你可以插入任意数量的钥匙。只有插入至少 把真钥匙时,X 门才会打开。
你已经对这些钥匙进行了 次测试。第 次测试的过程如下:
你将 把钥匙 插入了 X 门;
测试结果用一个英文字母 表示: 表示在第 次测试中 X 门打开了; 表示在第 次测试中 X 门没有打开。
一共有 种可能的钥匙组合,即每把钥匙可能是真钥匙或假钥匙。请在这些组合中,找出与任何测试结果都不矛盾的组合数量。
给定的测试结果有可能是错误的,此时没有任何组合满足条件,请输出 。
输入格式
第一行输入三个整数 $n,m,k \left(1 \leqq k \leqq n \leqq 15;\ 1 \leqq m \leqq 100\right)$ 代表钥匙数量、测试次数和打开 X 门所需的真钥匙数量。
此后 行,第 行先输入一个整数 代表第 次测试插入的钥匙数量,随后输入 个互不相同的整数 $a_{i,1},a_{i,2},\dots,a_{i,c_i} \left(1 \leqq a_{i,j} \leqq n\right)$ 代表插入的钥匙编号,最后输入一个字符 $r_i \left(r_i \in \{\texttt{`o'},\texttt{`x'}\}\right)$ 代表第 次测试的结果。
输出格式
在一行上输出一个整数,代表与任何测试结果都不矛盾的钥匙组合数量。
测试样例
3 2 2
3 1 2 3 o
2 2 3 x
2
样例 1 解释
此输入中共有三把钥匙,进行了两次测试,打开 X 门需要两把真钥匙。
第一次测试使用了钥匙 ,X 门打开了;
第二次测试使用了钥匙 ,X 门没有打开。
与测试结果都不矛盾的组合有两种:
钥匙 和钥匙 是真钥匙,钥匙 是假钥匙;
钥匙 和钥匙 是真钥匙,钥匙 是假钥匙。
因此输出 。
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
样例 2 解释
如题目描述所述,答案可能是 。
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