100 atcoder#ABC128C. [ABC128C] Switches

[ABC128C] Switches

题目描述

on と off の状態を持つ N N 個の スイッチと、M M 個の電球があります。スイッチには 1 1 から N N の、電球には 1 1 から M M の番号がついています。

電球 i i ki k_i 個のスイッチに繋がっており、スイッチ si1, si2, ..., siki s_{i1},\ s_{i2},\ ...,\ s_{ik_i} のうち on になっているスイッチの個数を 2 2 で割った余りが pi p_i に等しい時に点灯します。

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M k1 k_1 s11 s_{11} s12 s_{12} ... ... s1k1 s_{1k_1} : : kM k_M sM1 s_{M1} sM2 s_{M2} ... ... sMkM s_{Mk_M} p1 p_1 p2 p_2 ... ... pM p_M

输出格式

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせの個数を出力せよ。

题目大意

题目描述

nn 个开关和 mm 个灯泡,每个开关都处于“开”和“关”状态中的一种。开关从 11nn 编号,灯泡从 11mm 编号。

ii 号灯泡连接着 kik_i 个开关:开关 si,1s_{i,1}si,2s_{i,2},...,si,kis_{i,k_i}。当这些开关中,处于“开”状态的开关数量之和模 2 余 pip_i 时,这个灯泡就会被点亮。

有多少“开”和“关”的组合,可以点亮所有灯泡?

输入格式

输入来自以下格式的标准输入:


N N M M

k1 k_1 s1,1 s_{1,1} s1,2 s_{1,2} ... ... s1,k1 s_{1,k_1}

: :

kM k_M sM,1 s_{M,1} sM,2 s_{M,2} ... ... sM,kM s_{M,k_M}

p1 p_1 p2 p_2 ... ... pM p_M


输出格式

输出一个数,表示有多少总组合方案可以点亮所有灯泡。

说明/提示

数据范围

  • 1N,M101\le N,M \le 10

  • 1kiN1 \le k_i \le N

  • 1si,jN1 \le s_{i,j} \le N

  • si,asi,b(ab)s_{i,a} \neq s_{i,b} (a \neq b)

  • pip_i 只能是 0011

  • 上述所有值都是整数

样例 1/样例 4

  • 灯泡 11 当以下开关里开着的总数是偶数时会亮:开关 1122

  • 灯泡 22 当以下开关里开着的总数是奇数是会亮:开关 22

开关 1122 一共组成了四种组合:(开,开),(开,关),(关,开)和(关,关)。其中只有(开,开)满足要求,所以输出 11

样例 2/样例 5

  • 灯泡 11 当以下开关里开着的总数是偶数时会亮:开关 1122

  • 灯泡 22 当以下开关里开着的总数是偶数时会亮:开关 11

  • 灯泡 33 当以下开关里开着的总数是奇数时会亮:开关 22

为了点亮灯泡 22,开关 11 必须是关着的;为了点亮灯泡 33,开关 22 必须是开着的。但这样灯泡 11 就不能被点亮了。所以,没有组合能让所有灯泡亮起来,故输出 00

2 2
2 1 2
1 2
0 1
1
2 3
2 1 2
1 1
1 2
0 0 1
0
5 2
3 1 2 5
2 2 3
1 0
8

提示

制約

  • 1  N, M  10 1\ \leq\ N,\ M\ \leq\ 10
  • 1  ki  N 1\ \leq\ k_i\ \leq\ N
  • 1  sij  N 1\ \leq\ s_{ij}\ \leq\ N
  • sia  sib (a  b) s_{ia}\ \neq\ s_{ib}\ (a\ \neq\ b)
  • pi p_i 0 0 または 1 1
  • 入力は全て整数である

Sample Explanation 1

- 電球 1 1 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1, 2 1,\ 2 - 電球 2 2 は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ 2 2 (スイッチ 1 1 、スイッチ 2 2 ) の状態としては (on,on),(on,off),(off,on),(off,off) が考えられますが、このうち (on,on) のみが条件を満たすので、1 1 を出力してください。

Sample Explanation 2

- 電球 1 1 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1, 2 1,\ 2 - 電球 2 2 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1 1 - 電球 3 3 は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ 2 2 電球 2 2 を点灯させるためには スイッチ 1 1 が off, 電球 3 3 を点灯させるためにはスイッチ 2 2 が on である必要がありますが、この時電球 1 1 は点灯しません。 よって、全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは存在しないので、0 0 を出力してください。