← 返回题目列表

AtCoder · abc128_c

C. 开关

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

分数: 300 点

问题陈述

我们有 N 切换“开”和“关”状态,并且 M 灯泡。开关已编号 1 to N,灯泡编号 1 to M.

灯泡 i 连接到 k_i 开关:开关 s_{i1}, s_{i2}, ...,和 s_{ik_i}。当这些开关中“打开”的开关数量等于 p_i 模数 2.

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

约束

  • 1 \leq N, M \leq 10
  • 1 \leq k_i \leq N
  • 1 \leq s_{ij} \leq N
  • s_{ia} \neq s_{ib} (a \neq b)
  • p_i is 0 or 1.
  • 输入中的所有值都是整数。

输入

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

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

输出

打印点亮所有灯泡的开关的“开”和“关”状态的组合数。 当以下开关中有偶数个处于“打开”状态时,


示例输入 1

2 2
2 1 2
1 2
0 1

示例输出 1

1
  • 灯泡 1 会亮起: 开关 当以下开关中有奇数个“打开”时, 1 和 2.
  • 灯泡 2 会亮起: 开关 2.

有四种可能的状态组合(开关 1,开关 2):(开,开),(开,关),(关,开)和(关,关)。其中,只有(on, on)点亮所有灯泡,所以我们应该打印 1.


示例输入 2

2 3
2 1 2
1 1
1 2
0 0 1

示例输出 2

0
  • 灯泡 1 会亮起: 开关 当以下开关中有奇数个“打开”时, 1 和 2.
  • 灯泡 2 会亮起: 开关 当以下开关中有奇数个“打开”时, 1.
  • 灯泡 3 会亮起: 开关 2.

开关 1 必须“关闭”才能点亮灯泡 2 和开关 2 必须“打开”才能点亮灯泡 3,但是灯泡 1 不会亮起。因此,不存在点亮所有灯泡的开关状态组合,因此我们应该打印 0.


示例输入 3

5 2
3 1 2 5
2 2 3
1 0

示例输出 3

8