分数: 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