#ABC128C. 灯泡开关
灯泡开关
AT_abc128_c [ABC128C] Switches
题目描述
有 个开关和 个灯泡,每个开关都处于「开」和「关」状态中的一种。开关从 到 编号,灯泡从 到 编号。
第 个灯泡连接着 个开关 。当这些开关中处于「开」状态的开关数量对 取模的结果等于 时,这个灯泡就会被点亮。
请问有多少种「开」和「关」的组合,可以点亮所有灯泡?
输入格式
第一行输入两个整数 代表开关数量和灯泡数量。
此后 行,第 行先输入一个整数 代表第 个灯泡连接的开关数量,随后输入 个互不相同的整数 $s_{i,1},s_{i,2},\dots,s_{i,k_i} \left(1 \leqq s_{i,j} \leqq n\right)$ 代表这些开关的编号。
最后一行输入 个整数 代表第 个灯泡被点亮所需的奇偶性。
输出格式
在一行上输出一个整数,代表可以点亮所有灯泡的「开」和「关」组合数量。
测试样例
2 2
2 1 2
1 2
0 1
1
样例 1 解释
灯泡 连接开关 和 ,当这两个开关中处于「开」状态的开关数量为偶数时点亮();灯泡 连接开关 ,当开关 处于「开」状态时点亮()。
开关 和 一共有 种组合,其中只有(开,开)能同时点亮两个灯泡,所以输出 。
2 3
2 1 2
1 1
1 2
0 0 1
0
样例 2 解释
灯泡 连接开关 和 ,要求其中处于「开」状态的开关数量为偶数;灯泡 连接开关 ,要求开关 处于「开」状态;灯泡 连接开关 ,要求开关 处于「开」状态。
为了点亮灯泡 ,开关 必须是关着的;为了点亮灯泡 ,开关 必须是开着的。但这样灯泡 对应的「开」状态开关数量为 ,是奇数,灯泡 不能被点亮。所以没有组合能让所有灯泡亮起来,输出 。
5 2
3 1 2 5
2 2 3
1 0
8