#ABC356C. 钥匙谜题

钥匙谜题

AT_abc356_c [ABC356C] Keys

题目描述

\hspace{15pt}你有 nn 把编号为 1,2,…,n1,2,\dots,n 的钥匙,其中一些是真钥匙,其余都是假钥匙。

\hspace{15pt}有一扇 X 门,你可以插入任意数量的钥匙。只有插入至少 kk 把真钥匙时,X 门才会打开。

\hspace{15pt}你已经对这些钥匙进行了 mm 次测试。第 ii 次测试的过程如下:

∙ \hspace{23pt}\bullet\,你将 cic_i 把钥匙 ai,1,ai,2,…,ai,cia_{i,1},a_{i,2},\dots,a_{i,c_i} 插入了 X 门;

∙ \hspace{23pt}\bullet\,测试结果用一个英文字母 rir_i 表示:ri=‘o’r_i=\texttt{`o'} 表示在第 ii 次测试中 X 门打开了;ri=‘x’r_i=\texttt{`x'} 表示在第 ii 次测试中 X 门没有打开。

\hspace{15pt}一共有 2n2^n 种可能的钥匙组合,即每把钥匙可能是真钥匙或假钥匙。请在这些组合中,找出与任何测试结果都不矛盾的组合数量。

\hspace{15pt}给定的测试结果有可能是错误的,此时没有任何组合满足条件,请输出 00。

输入格式

\hspace{15pt}第一行输入三个整数 $n,m,k \left(1 \leqq k \leqq n \leqq 15;\ 1 \leqq m \leqq 100\right)$ 代表钥匙数量、测试次数和打开 X 门所需的真钥匙数量。

\hspace{15pt}此后 mm 行,第 ii 行先输入一个整数 ci(1≦ci≦n)c_i \left(1 \leqq c_i \leqq n\right) 代表第 ii 次测试插入的钥匙数量,随后输入 cic_i 个互不相同的整数 $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)$ 代表第 ii 次测试的结果。

输出格式

\hspace{15pt}在一行上输出一个整数,代表与任何测试结果都不矛盾的钥匙组合数量。

测试样例

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

样例 1 解释

\hspace{15pt}此输入中共有三把钥匙,进行了两次测试,打开 X 门需要两把真钥匙。

∙ \hspace{23pt}\bullet\,第一次测试使用了钥匙 1,2,31,2,3,X 门打开了;

∙ \hspace{23pt}\bullet\,第二次测试使用了钥匙 2,32,3,X 门没有打开。

\hspace{15pt}与测试结果都不矛盾的组合有两种:

∙ \hspace{23pt}\bullet\,钥匙 11 和钥匙 33 是真钥匙,钥匙 22 是假钥匙;

∙ \hspace{23pt}\bullet\,钥匙 11 和钥匙 22 是真钥匙,钥匙 33 是假钥匙。

\hspace{15pt}因此输出 22。

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 解释

\hspace{15pt}如题目描述所述,答案可能是 00。

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