Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

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.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

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

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    check = True
    for j in range(m):
        light = 0
        for k in range(1, len(l[j])):
            if ((i >> l[j][k] - 1) & 1):
                light += 1
        if light % 2 != p[j]:
            check = False
    if check:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    s = LIR(m)
    p = LI()
    ans = 0
    for i in range(m):
        s[i] = sum([1<<(j-1) for j in s[i][1:]])
    for b in range(1<<n):
        for i in range(m):
            if bin(s[i]&b).count("1")&1 != p[i]:
                break
        else:ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
P = LIST()

import itertools
#L = [0, 1] #生成する数字
num = N #生成するビット数
bit_list = list(itertools.product([0, 1], repeat=num))
#print(bit_list)
ans = 0
#print(L[0][0])
on = 0
for bit in bit_list:
    # ココ注意
    cnt = 0
    for i in range(M):
        #print(L[i][1:])
        wa = 0
        on = 0
        for s in L[i][1:]:
            on ^= bit[s-1]
        # wa == P[i]なら，その電球は点灯する
        if P[i] == on:
            cnt += 1
        #if cnt == L[i][0]:
        #    c += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
P = LIST()

import itertools
#L = [0, 1] #生成する数字
num = N #生成するビット数
bit_list = list(itertools.product([0, 1], repeat=num))
#print(bit_list)
ans = 0
#print(L[0][0])
on = 0
for bit in bit_list:
    # ココ注意
    cnt = 0
    for i in range(M):
        #print(L[i][1:])
        wa = 0
        on = 0
        for s in L[i][1:]:
            on += bit[s-1]
        # wa == P[i]なら，その電球は点灯する
        if P[i] == on % 2:
            cnt += 1
        #if cnt == L[i][0]:
        #    c += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
K = []
S = []
for i in range(M):
    tmp = LIST()
    K.append(tmp[0])
    S.append(tmp[1:])
P = LIST()

switch_patern = []
for i in range(2**N):
    tmp = format(i, '0'+str(N)+'b')
    tmp = [int(t) for t in tmp]
    switch_patern.append(tmp)

count = 0
for i in range(2**N):
    flag = 0
    for j in range(M):
        tmp = 0
        for k in range(K[j]):
            tmp += switch_patern[i][S[j][k]-1]
        if tmp % 2 == P[j]:
            flag += 1
    if flag == M:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
s = [LIST() for i in range(M)]
p = LIST()

num = N
bits = product([0, 1], repeat=num)

co = 0
for x in bits:
	a = [0]*M
	for i in range(len(s)):
		for j in range(len(s[i]) - 1):
			if x[s[i][j + 1] - 1] == 1:
				a[i] += 1
	f = True
	for i in range(len(a)):
		if a[i]%2 == p[i]:
			pass
		else:
			f = False
	if f:
		co += 1

print(co)

Submission status: Accepted

Solution code:
from collections import deque


n, m = map(int, input().split())
s = [0] * m
k = [0] * m
for i in range(m):
    s[i] = deque(map(int, input().split()))
    k[i] = deque.popleft(s[i])
    s[i] = list(s[i])
p = list(map(int, input().split()))
cnt = 0
for i in range(2 ** n):
    l = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            l[j] = 1
    for k in range(m):
        total = 0
        ans = True
        for num in s[k]:
            idx = num - 1
            if l[idx] == 1:
                total += 1
        if total % 2 != p[k]:
            ans = False
            break
    if ans:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n,m = map(int, input().split())
    KSMs = [list(map(int, input().split())) for i in range(m)]
    Ps = list(map(int, input().split()))
    cnt = 0
    # print(KSMs)
    is_ok = True
    #各スイッチのon/offパターンをすべて探索する
    for i in range(pow(2,n)):
        if not is_ok:
            is_ok = True
        for j in range(m):
            km = KSMs[j][0]
            # j個めの電球は，km個のスイッチに繋がれている

            cnt2 = 0
            for k in range(km):
                # 各スイッチのonになっている個数を数える
                # bitのKSMs[j][k+1]-1桁目が1の場合on0の場合false
                # print(KSMs[j][k+1]-1)
                if ((i>> (KSMs[j][k+1]-1)) & 1):
                    cnt2 += 1
            if cnt2 % 2 != Ps[j]:
                # j個目の電球は点灯していない
                is_ok = False
                break
        if is_ok:
            cnt += 1
            #print(bin(i))
               
    print(cnt)

    # 予約を断る
    # 次は土日か19の午後
    # 
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
例えばスイッチが2つあった場合、on,offの組み合わせをビットで表すと
00
01
10
11
の4通りで、右からスイッチ1,2とすると
1を左に0ビットシフトしたものが01
1を左に1ビットシフトしたものが10
となり、それぞれスイッチ1がonの状態と
スイッチ2がonの状態を表すことができる
これを利用する
'''

n, m = map(int,input().split())
s = []
for _ in range(m):
    s.append([int(i) for i in input().split()])
p = [int(i) for i in input().split()]

ans = 0
for i in range(2**n):
    ok = True
    for j in range(m):
        cnt = 0
        for k in range(1,s[j][0]+1):
            if i & (1 << (s[j][k]-1)):
                cnt += 1
        if cnt % 2 != p[j]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()

sen = []
for i in range(m):
    sen.append(li())

p = li()
ans = 0

#全通り
for i in range(2**n):
    swc = []
    # １通りの中の各桁について
    for j in range(n):
        # print((i>>j) & 1)
        swc.append((i>>j) & 1)
    # print(swc)
    
    # 各電球について
    for j in range(m):
        l = sen[j]
        km = l[0]
        on_cnt = 0
        for k in l[1:]:
            if swc[k-1]:
                on_cnt += 1
        if on_cnt%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())

switch_list = []
for i in range(M):
    k = list(map(int, input().split()))
    k = k[1:]
    switch_list.append(k)

p = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    all_flg = 1
    on_list = []
    for j in range(M):
        flg = False
        for s in switch_list[j]:
            if (i >> (s-1)&1):
                flg = not flg
        if p[j] != flg:
            all_flg = 0
            break
    if all_flg:
        ans += 1    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())

light_list = []
for i in range(M):
    k = list(map(int, input().split()))
    k = k[1:]
    light_list.append(k)

p = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    on_list = []
    for j in range(N):
        if ((i>>j) & 1):
            on_list.append(j+1)
    for k in range(M):
        if p[k] == 0:
            flg = True
        else:
            flg = False    
        for l in range(len(light_list[k])):
            if light_list[k][l] in on_list:
                flg = not flg
        if not flg:
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
L = []
S = []
N, M = map(int, input().split())
cnt = 0
ans = 0
for i in range(M):
    l = list(map(int, input().split()))
    L.append(l)
p = list(map(int, input().split()))

for j in range(2**N):
    switch = [0]*N
    for k in range(N):
        if (j >> k) & 1:
            switch[k-1]=1
    S.append(switch)
    #ここまでで全パターン
#あるパターンにおいて全点灯しているか？

for i in range(2**N):
    I = [0]*M
    cnt = 0
    for k in range(M):
        for x in range(1, len(L[k])):
            if S[i][L[k][x]-1]==1:
                I[k]+=1
    for i in range(M):
        if I[i]%2==p[i]:
            cnt +=1
    if cnt == M:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
switches = [list(map(lambda x: int(x) - 1, input().split(' ')))[1:]
            for _ in range(m)]
p = list(map(int, input().split(' ')))

cnt = 0
# ビット演算子。n ビット左シフト
for condition in range(1 << n):
    light = True
    for i in range(m):
        oncnt = 0
        # for switch in switches:
        #   for i in switch:
        # の節約になる
        for switch in switches[i]:
            # ビット演算子。1 をフラグとした時、被っていれば != 0
            if (condition & (1 << switch)) != 0:
                oncnt += 1

        if oncnt % 2 != p[i]:
            light = False

    if light:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
light=[]
for _ in range(M):
    light.append(list(map(int,input().split())))
on_off=list(map(int,input().split()))
ans=0
for i in range(2**N):
    flag=True
    swi=[]
    for k in range(N):
        swi.append(i%2)
        i//=2

    for l_n in range(len(light)):
        cnt=0
        for j in range(light[l_n][0]):
            cnt+=swi[light[l_n][j+1]-1]
        if cnt%2!=on_off[l_n]:
            flag=False
    if flag:
        ans+=1    
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switches = []

for i in range(M):
    tmp = list(map(int,input().split()))
    tmp.pop(0)
    switches.append(tmp)

R = list(map(int,input().split()))

a = [list(format(i, '0%db' % N)) for i in range(2**N)]

ans = 0

for i in a:
    flag = 0
    for j in range(M):
        SUM = 0
        for k in switches[j]:
            SUM += int(i[k-1])
        if SUM%2 != R[j]:
            flag = 1
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 電球に対するスイッチの対応関係は、
# [[k1に対応するスイッチ],[k2に対応するスイッチ][k3に対応するスイッチ]...]
# みたいにする
switchToBulb = []
for _ in range(M):
  l = list(map(int, input().split()))
  l.pop(0)
  switchToBulb.append(l)

table = list(map(int, input().split()))

# 全探索しよう
# bit全探索を行う
# スイッチのパターンで全探索を行う
count = 0
for i in range(2 ** N):
    onSwitch = []
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            onSwitch.append(j + 1)  # フラグが立っていたら bag に果物を詰める
    
    check = [0 for _ in range(1, M+1)]
    for number in onSwitch:
      for index in range(len(switchToBulb)):
        if number in switchToBulb[index]:
          check[index] += 1

    check = [0 if i % 2 == 0 else 1 for i in check]

    if check == table:
      count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int,input().split())
switchs = {}
for i in range(m):
  switchs[i] = set(list(map(int,input().split()))[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(pow(2,n)):
  l = [0] * m
  for b in range(n):
    if (i&(1<<b)):
      #b番目のスイッチがon
      for j in range(m):
        if ((b+1) in switchs[j]):
          l[j] += 1
  s = 0
  for k in range(m):
    if (l[k]%2 == p[k]):
      s += 1
  if (s == m):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
r = 0
N, M = map(int, input().split())
sw_p = [0 for _ in range(N)]
for i in range(M):
  ks = list(map(int, input().split()))
  for s in ks[1:]:
    sw_p[s-1] |= 1 << i

P = list(map(int, input().split()))
p = 0
for i in range(M):
  p |= P[i] << i

for j in range(1 << N):
  t = 0
  for k in range(N):
    if j >> k & 1:
      t ^= sw_p[k]
  if t == p:
    r += 1

print(r)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
k = []
for i in range(m):
    s.append(list(map(int,input().split())))
    k.append(s[i].pop(0))
p = [int(i) for i in input().split()]

ans = 0
for i in range(2**n):
    ok = True
    for j in range(m):
        cnt = 0
        for l in range(k[j]):
            if i & (1 << (s[j][l]-1)):
                cnt += 1
        if cnt % 2 != p[j]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

s = []

for i in range(m):
    array = list(map(int, input().split()))
    s.append(array[1:])

check = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    flag =True
    for j in range(m):
        a = 0
        for k in range(n):
            if ((i >>k)&1) == 1 and k+1 in s[j]:
                a += 1
        if a%2 == check[j]:
            continue
        else:
            flag = False
            break
    if flag is True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
zentai=0
for i in range(M):
    K=list(map(int,input().split()))
    S.append(K[1:])
P=list(map(int,input().split()))
for i in range(2**N):
    switch=["off"]*N
    count=0
    ON_switch=[]
    for j in range(N):
        if ((i>>j)&1):
            ON_switch.append(j+1)
    """ for k in range(N):
        if switch[k]=="on": """            
    for m in range(M):
        cnt=0
        for n in range(len(S[m])):
            if S[m][n] in ON_switch:
                cnt+=1
        else:
            if cnt%2==P[m]:
                count+=1
    else:
        if count==M:
            zentai+=1
print(zentai)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ks = [list(map(int, input().split()))for i in range(M)]
p = list(map(int, input().split()))
cnt = 0
all_on = 1
ans = 0
for i in range(2**N):
    all_on = 1
    bits = "0" + str(N) + "b" 
    sw_line = str(format(i,bits))
    for j in range(M):
        for k in range(1,ks[j][0]+1):
            sw = sw_line[ks[j][k]-1]
            if(sw== "1"):
                cnt += 1
        if(cnt % 2 != p[j]):
            all_on = 0
        cnt = 0
    if(all_on == 1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()] #Nがスイッチの数、Mは電球の数
sss = []
for i in range(M):
    buff = [int(i) for i in input().split()][1:]
    onoff = 0
    for b in buff:
        onoff += 1<<(b-1)
    sss.append(onoff)

ppp = [int(i) for i in input().split()]

ct=0
for i in range(1<<N):
    for s,p in zip(sss,ppp):
        if bin(i&s).count("1")%2!=p:
            break
    else:
        ct+=1

print(ct)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
switches = []
for i in range(M):
    buff = 0
    k,*sss = [int(i) for i in input().split()]
    for s in sss:
        buff += 1 << (s-1)
    switches.append(buff)

ppp = [int(i) for i in input().split()]
ans = 0
for i in range(1<<N):
    for p,s in zip(ppp,switches):
        buff = s&i
        buff = bin(buff).count("1")%2
        if buff != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()] #Nがスイッチの数、Mは電球の数
sss = []
for i in range(M):
    buff = [int(i)-1 for i in input().split()][1:]
    onoff = [0 for i in range(N)]
    for j in buff:
        onoff[j]=1
    sss.append(onoff)

ppp = [int(i) for i in input().split()]

ct=0
for i in range(1<<N):
    bitcode = [int(i) for i in list(bin(i)[2:].zfill(N))]
    for s,p in zip(sss,ppp):
        if sum(j*k for j,k in zip(s,bitcode))%2!=p:
            break
    else:
        ct+=1

print(ct)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

switches = []

for i in range(m):
    array = list(map(int, input().split()))
    switches.append(array[1:])

checker = list(map(int, input().split()))

bit_size = 2 ** n

ans = 0

for i in range(bit_size):
    num = format(i, 'b').zfill(n)
    flag = True
    for j in range(m):
        a = 0
        for k in range(n):
            if num[k] == '1' and k+1 in switches[j]:
                a += 1
        if a % 2 == checker[j]:
            continue
        else:
            flag = False
            break
    if flag is True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
S=[]
for i in range(m):
  S.append([int(i) for i in input().split()])
P=[int(i) for i in input().split()]
ans=0
for i in range(2**n):
  t=0
  for j in range(m):
    p=0
    for k,s in enumerate(S[j]):
      if k==0:
        continue
      else:
        if i&(1<<(s-1)):
          p+=1
    if p%2==P[j]:
      t+=1
  if t==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline

n, m = map(int, input().split())
s = []
p = [0] * m
cnt_k = 0
cnt_j = 0
ans = 0

for i in range(m):
    s_k = list(map(int, input().split()))
    s.append(s_k)
    
p = list(map(int, input().split()))

memo = list(itertools.product([0, 1], repeat=n))
for i in range(2 ** n):
    for j in range(m):
        for k in range(1, s[j][0] + 1):
            if memo[i][s[j][k] - 1] == 1:
                cnt_k += 1

        if cnt_k % 2 == p[j]:
            cnt_j += 1
        cnt_k = 0

    if cnt_j == m:
        ans += 1

    cnt_j = 0
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = []
k = []

for _ in range(M):
    tmp = list(map(int, input().split()))
    k.append(tmp.pop(0))
    s.append(tmp)
p = list(map(int, input().split()))
counter = 0

for bit in range(1 << N):
    hantei = True
    for n1, j in enumerate(s):
        tmp = 0
        for i in j:
            if(bit & (1 << (i-1))):
                tmp += 1
        if(tmp % 2 != p[n1]):
            hantei = False
    if(hantei == True):
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
lst = [[] for _ in range(m)]
for i in range(m):
    a = list(map(int,input().split()))
    a.pop(0)
    lst[i] = copy.copy(a)
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
    switch = [0 for _ in range(n)]
    for j in range(n):
        if i >> j & 1:
            switch[j] = 1
    for j in range(m):
        light = 0
        for k in range(len(lst[j])):
            if switch[lst[j][k]-1] == 1:
                light += 1
        if light % 2 != p[j]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
light_data = [[int(x) for x in input().split()][1:] for _ in range(m)] #読み込んだ行の先頭のデータは削除する
p_data = [int(x) for x in input().split()]

count = 0
for i in range(2**n):
    switch_state = i
    for i,l_data in enumerate(light_data):
        on_switch = 0
        for light_num in l_data:
            
            if switch_state & 1<<(light_num - 1):
                on_switch += 1
        
        if on_switch%2 == p_data[i]:
            continue
        else:
            break
            
    else: # M個の電球が全て点灯していたらcountを増やす
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
Switches = np.zeros((N,M)) # N = Switch, M = light

for i in range(M):
    arr = list(map(int, input().split()))
    for item in arr[1:]:
        Switches[item-1, i] = 1
Ps = np.array(list(map(int, input().split())))


bit_max = 2 ** N
stat = np.zeros(M)
cnt = 1 if (stat == Ps).all() else 0

for i in range(1, bit_max):
    bits = [j for j in range(N) if (i >> j &1)]
    res = stat + Switches[bits].sum(axis=0) % 2
    cnt += 1 if (res == Ps).all() else 0

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0

def dfs(i, sw):
    global ans
    if i == n:
        if judge(sw):
            ans += 1
    else:
        dfs(i+1, sw+'0')
        dfs(i+1, sw+'1')

def judge(sw):
    """
    全ての電球が点灯するかどうかを判定
    """
    for values in ks:
        cnt = 0
        for i in values[1:]:
            if sw[i-1] == '1':
                cnt += 1
        if cnt%2 != p[ks.index(values)]:
            return False
    return True

dfs(0, '')
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
zentai=0
for i in range(M):
    K=list(map(int,input().split()))
    S.append(K[1:])
P=list(map(int,input().split()))
for i in range(2**N):
    switch=["off"]*N
    count=0
    for j in range(N):
        if ((i>>j)&1):
            switch[N-j-1]="on"
    ON_switch=[]
    for k in range(N):
        if switch[k]=="on":
            ON_switch.append(k+1)
    for m in range(M):
        cnt=0
        for n in range(len(S[m])):
            if S[m][n] in ON_switch:
                cnt+=1
        else:
            if cnt%2==P[m]:
                count+=1
    else:
        if count==M:
            zentai+=1
print(zentai)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class Lights:

    def __init__(self):
        self.lights = []

    def add(self, light):
        self.lights.append(light)

    def is_all_up(self, switch):
        for light in self.lights:
            if not light.is_up(switch):
                return False
        return True

    def __str__(self):
        result = "{"
        for light in self.lights:
            result += str(light)
        return result + "}"


class Light:

    def __init__(self, k, s, p):
        self.k = k
        self.s = s
        self.p = p

    def is_up(self, switch):
        intersection = self.s.intersection(switch)
        return self.p == len(intersection) % 2

    def __str__(self):
        return "[k={}, s={}, p={}]".format(self.k, self.s, self.p)


def main():
    n, m = map(int, input().split())
    ks_lst = [list(map(int, input().split())) for _ in range(m)]
    p_lst = list(map(int, input().split()))
    lights = Lights()
    for ks, p in zip(ks_lst, p_lst):
        k, s = ks[0], set(ks[1:])
        lights.add(Light(k, s, p))

    ans = 0
    for bit in range(2**n):
        switches = set()
        for i in range(n+1):
            if (bit >> i) & 1:
                switches.add(i+1)
        if lights.is_all_up(switches):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
k = []
s = []
for i in range(M) :
    ks = list(map(int,input().split()))
    k.append(ks[0])
    s.append(ks[1:])
p = [int(x) for x in input().split()]

ans = 0
for i in range(2**N) :
    pat = str("{:0>{}b}".format(i, N))
    flag = True
    for j in range(M) :
        swit = 0
        for x in range(k[j]) :
            if pat[s[j][x]-1] == "1" :
                swit += 1
        if swit%2 != p[j] :
            flag = False
    if flag == True :
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
s = []
for _ in range(M):
    t = list(map(int, input().split()))
    t.pop(0)
    s.append(t)

p = list(map(int, input().split()))

count = 0
for i in range(2 ** N):
    c = bin(i)[2:]
    c = '0' * (N - len(c)) + c if len(c) < N else c
    u = []
    for j, l in enumerate(s):
        tmp = [int(c[k-1]) for k in l]
        u.append(sum(tmp) % 2)

    if u == p:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
s = [LIST()[1:] for _ in range(M)]
p = LIST()

ans = 0
for x in product([0, 1], repeat=N):
    for i in range(M):
    	cnt = 0
    	for n in s[i]:
    		if x[n-1] == 1:
    			cnt += 1
    	if cnt%2 != p[i]:
    		break
    else:
    	ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ks = [tuple(int(x) for x in stdin.readline().rstrip().split())[1:] for _ in range(M)]
    ps = [int(x) for x in stdin.readline().rstrip().split()]

    max_ = int('1' * N, 2)
    result = 0
    for i in range(max_ + 1):
        b = bin(i)[2:]
        b = '0' * (N - len(b)) + b
        for idx in range(M):
            on_count = 0
            for j in [x - 1 for x in ks[idx]]:
                if b[j] == '1':
                    on_count += 1
            if on_count % 2 == ps[idx]:
                pass
            else:
                break
        else:
            result += 1
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(2 ** N):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(np.sum(pattern[S[j] -1 ]) % 2 == P[j] for j in range(M)):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

S = []
for _ in range(M):
    s = tuple(map(lambda a: int(a) - 1, input().split()))[1:]
    S.append(s)

P = tuple(map(int, input().split()))

ans = 0
for state in range(1 << N):
    for p, s in zip(P, S):
        cnt = 0
        for i in s:
            cnt += 1 if (state & (1 << i)) > 0 else 0
        if cnt % 2 != p:
            break
    else:
        ans += 1

print(ans)