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:
from itertools import accumulate, product, permutations, combinations
def solve():
    N, M = map(int, input().split())
    A = [list(map(int,input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    ans = 0
    for p in product([0,1],repeat = N):
        for i in range(M):
            xor = 0
            for j in range(1,A[i][0]+1):
                xor ^= p[A[i][j]-1]
            if xor != P[i]:
                break
        else:
            ans += 1
    return ans
print(solve())

Submission status: Accepted

Solution code:
def bitcount(x):
    r = 0
    l = len(bin(x))-2
    for i in range(l):
        if x>>i&1:r+=1
    return r
n,m = map(int,input().split())
switch = [0]*m
for i in range(m):
    tmp = list(map(int,input().split()))[1:]
    for s in tmp:
        switch[i] = switch[i]|2**(s-1)

P = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    ons = 0 #ついてる電球
    for j in range(m):#j番目の電球について
        tmp = i&switch[j]
        if bitcount(tmp)%2==P[j]:
            ons+=1
    if ons==m:ans+=1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
L=[list(map(int,input().split()))[1:] for _ in range(m)]
P=list(map(int,input().split()))
cnt=0
for i in range(2**n):
    on=bin(i)[2:].zfill(n)
    for l,p in zip(L,P):
        if sum(int(on[s-1]) for s in l)%2!=p:
            break
    else:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
lamps = [[x-1 for x in i_l()[1:]] for _ in range(M)]
p = i_l()
ans = 0

for bit in range(1<<N):
    flag = True
    for i in range(M):
        cnt = 0
        for j in range(N):
            if bit & 1 << j and j in lamps[i]:
                cnt += 1
        if cnt % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2**n):
    for j in range(m):
        switch = 0
        for k in range(n):
            if (i >> k & 1) and k+1 in s[j]:
                switch += 1
        if switch % 2 != p[j]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int,input().split())
k = []
for i in range(M):
    k.append(list(map(int,input().split())))
p = list(map(int,input().split()))
ks = [i[0] for i in k]
ss = [i[1:] for i in k]

prods = list(itertools.product([0, 1], repeat=N))
count = 0
for prod in prods:
  check = 0
  for i in range(M):
    s = ss[i]
    # sごとに
    n = sum([prod[j-1] for j in s])
    if n % 2 == p[i]:
      check += 1
  if check == M:
    count += 1
print(count)

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))

res = 0
for i in range(2**N):
    sw = [0]*N
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            sw[j] = 1
    
    for i, ksi in enu(ks):
        sumv = 0
        for s in ksi[1:]:
            sumv += sw[s-1]
        if sumv%2 != p[i]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

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

slist=[]
for i in range(M):
  k,*sl=list(map(int,input().split()))
  sw=[0]*N
  for s in sl:
    sw[s-1]=1
  slist.append(sw)
  
qlist=list(map(int,input().split()))
#print(slist)
#print(qlist)

answer=0
for bit in itertools.product(range(2),repeat=N):
  for i in range(M):
    parity=0
    for j in range(N):
      parity+=slist[i][j]&bit[j]
    if qlist[i]!=parity%2:
      break
  else:
    answer+=1
    
print(answer)

Submission status: Accepted

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

S = []
for _ in range(M):
    K = list(map(int, input().split()))
    S.append(K[1:])

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

ans = 0
for i in range(2 ** N):
    on_switch = []
    for j in range(N):
        if ((i >> j) & 1):
            on_switch.append(j + 1)
    clear = True
    for k, s in enumerate(S):
        res = 0
        for si in s:
            if si in on_switch:
                res += 1
        if res % 2 != P[k]:
            clear = False
            break
    if clear:
        ans += 1

print(ans)

Submission status: Accepted

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

x = []
for i in range(2**n):
    temp = []
    for j in range(n):
        if i>>j & 1:
            temp.append(j+1)
    x.append(temp)

l = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

z = 0
for a in range(2**n):
    for b in range(m):
        y = 0
        for c in range(l[b][0]):
            if l[b][c+1] in x[a]:
                y += 1
        if y % 2 != p[b]:
            break
    else:
        z += 1

print(z)

Submission status: Accepted

Solution code:
# solution
import io

n,m = map(int,input().split())
S = []
for _ in range(m):
  s = list(map(int,input().split()))
  del s[0]
  k = 0
  for i in s:
    k +=  1<<(i-1)
  S.append(k)

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

qwe = [[] for _ in range(m+1)]
qwe[0] = [i for i in range(2**n)]
for i in range(m):
  for j in qwe[i]:
    if str(bin(j & S[i])).count('1')%2==p[i]:
      qwe[i+1].append(j)
      
print(len(qwe[m]))

Submission status: Accepted

Solution code:
from itertools import product
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M = map(int, readline().split())
    S = [[int(i) for i in readline().split()] for _ in range(M)]
    P = [int(i) for i in readline().split()]

    ans = 0
    A = [[0, 1] for _ in range(N)]
    for pattern in product(*A):
        on = []
        for s in S:
            tmp = 0
            for i in range(s[0]):
                tmp += pattern[s[i+1]-1]
            on.append(tmp % 2)

        if on == P:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0
pattern = [0]*N

def dfs(pattern, pos):
    if pos == N:
        for i in range(M):
            num , *switches = ks[i]
            if sum([pattern[sw-1] for sw in switches]) % 2 != P[i]:
                break
        else:
            global cnt
            cnt += 1
    else:
        pattern[pos] = 0
        dfs(pattern, pos+1)
        pattern[pos] = 1
        dfs(pattern, pos+1)
        
dfs(pattern, 0)
print(cnt)

Submission status: Accepted

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

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

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

ans = 0
for j in range(2**n):
    tmp_sw = bin(j)[2:].zfill(n)
    #print(tmp_sw)

    break_on = 0
    for k in range(m):
        tmp = 0
        #print(s[k])
        for h in s[k]:
            if tmp_sw[h-1] == '1':
                tmp += 1
        #print(tmp)
        if tmp % 2 != p[k]:
            break_on = 1
    
    if break_on == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

from itertools import product

N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0

#for i in range(2**N):
    #x = bin(i)[2:].zfill(N)
    #l = list(map(int, list(x)))
for l in product([0, 1], repeat=N):
    for i in range(M):
        num , *switchs = ks[i]
        if sum([l[sw-1] for sw in switchs]) % 2 != P[i]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0
for i in range(2**N):
    x = bin(i)[2:].zfill(N)
    l = list(map(int, list(x)))
    flag = 1
    for i in range(M):
        num , *switchs = ks[i]
        if sum([l[sw-1] for sw in switchs]) % 2 != P[i]:
            flag = 0
            break
    if flag:
        cnt += 1

print(cnt)

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()))
ans = 0
# print(ks)
for i in range(2**n):
    bulb = [0]*m
    bin_str = format(i, '010b')
    for j in range(m):
        cnt = 0
        for k in ks[j][1:]:
            # print(k)
            if bin_str[-k] == "1":
               cnt += 1 
        if cnt % 2 == p[j]:
            # print(cnt)
            bulb[j] = 1
    # print(bin_str)
    # print(bulb)
    if bulb == [1]*m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = []
for i in range(M):
    S = list(map(int,input().split()))
    k,s = S[0],S[1:]
    K.append(s)
P = list(map(int,input().split()))

ans = 0
for i in range(pow(2,N)):
    Sw = []
    n = i
    for j in range(N):
        Sw.append(n%2)
        n//=2
    A = 0
    for k in range(M):
        n = 0
        for j in K[k]:
            n+=Sw[j-1]
        if n%2==P[k]:
            A+=1
    if A==M:ans += 1
print(ans)

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

for i in range(2**n):
    on = [0 for _ in range(n)]
    
    for j in range(n):
        if ((i>>j)&1):
            on[j] = 1
    all_on = True
    for j in range(m):
        on_num = 0
        for s in ks[j][1:]:
            if on[s-1]==1:
                on_num = on_num + 1
                
        if on_num%2 != p[j]:
            all_on = False
            break
    if all_on:
        ans = ans+1
print(ans)

Submission status: Accepted

Solution code:
t = input().rstrip().split(' ')
switch = int(t[0])
lamp = int(t[1])
s = [list(map(int, input().split())) for _ in range(lamp)]
p = list(map(int, input().split()))
ans = 0

for i in range(2 ** switch):
    ptn = bin(i)[2:].rjust(switch, '0')
    light = True
    for j in range(lamp):
        temp = 0
        for n in range(1, s[j][0] + 1):
            if ptn[s[j][n] - 1] == '1':
                temp += 1
        if temp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
t = input().rstrip().split(' ')
switch = int(t[0])
lamp = int(t[1])
s = [list(map(int, input().split())) for _ in range(lamp)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

for i in range(2 ** switch):
  ptn = bin(i)[2:].rjust(switch, "0")
  light = True;
  for j in range(lamp):
    temp = 0
    for n in range(1, s[j][0] + 1):
      if ptn[s[j][n] - 1] == "1":
        temp += 1
    if temp % 2 != p[j] %2:
      light = False
  if light:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n)]
for i in range(m):
    for s in [int(x) for x in sys.stdin.readline().split()][1:]:
        graph[s-1].append(i)
*p, = map(int, sys.stdin.readline().split())

def main():
    cnt = 0
    for i in range(1 << n):
        bits = [0] * m
        for j in range(n):
            if i >> j & 1:
                for s in graph[j]:
                    bits[s] ^= 1
        for j in range(m):
            if bits[j] ^ p[j]: break
        else:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
km=[list(map(int, input().split())) for _ in range(m)]
p=list(map(int, input().split()))
e=0
for i in range(2 ** n):
    b=0
    d=0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            b+= 10**j # フラグが立っていたら bag に果物を詰める
    if 1==1:
        b="0"*(n-len(str(b)))+str(b)
    for j in range(m):
        c=0
        for k in range(1,km[j][0]+1):
            b=str(b)


            f=int(b[(km[j][k]-1)])

            c+=f
        if c%2!=p[j]:
            break
        else:
            d+=1
    if d==m:
        e+=1
print(e)

Submission status: Accepted

Solution code:
def switches(N, M, array, P):
    count = 0
    for i in range(0,2**N):
        flag = 0
        for j in range(M):
            sum = 0
            for k in range(1,array[j][0]+1):
                if format(i, '0'+str(N)+'b')[array[j][k]-1] == '1':
                    sum += 1
            
            if sum%2 == P[j]:
                flag += 1
            
        if flag == M:
            count += 1

    return count


if __name__ == "__main__":
    N,M = map(int, input().split())
    array = []
    for i in range(M):
        array.append(list(map(int, input().strip().split())))
    P = list(map(int, input().strip().split()))
    print(switches(N,M,array,P))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def is_nth_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        k, *s = map(int, input().split())
        s = [i - 1 for i in s]
        S.append(s)
    P = list(map(int, input().split()))

    ans = 0
    for pattern in range(2 ** N):
        switch = []
        for i in range(N):
            switch.append(is_nth_set(pattern, i))

        for i in range(M):
            cnt = 0
            for s in S[i]:
                cnt += switch[s]
            if cnt % 2 != P[i]:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    # 各電球 i について、 si1, si2, ..., sik のうち、 onのスイッチが何個かを数える
    # それが偶数か奇数かによって、電球 i が付いているかどうかが分かる
    A = []
    for i in range(m):
        A.append(list(map(lambda x: int(x) - 1, input().split()))[1:])
    P = readInts()
    ans = 0

    for bit in range(1 << n):
        ok = True
        for i in range(m):
            con = 0
            for v in A[i]:
                #print(v)
                if bit & 1 << v:
                    con += 1
            if con % 2 != P[i]:
                ok = False
        if ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:


n,m=map(int,input().split())
K=[list(map(int,input().split())) for _ in range(m)]
P=list(map(int,input().split()))

ans = 0

for bits in range(2 ** n):
    ok = True
    for i, k in enumerate(K):
        ok = ok and sum((bits >> (s - 1)) & 1 for s in k[1:]) % 2 == P[i]
    if ok:
        ans += 1
        

print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(1<<n):
    isOn = []
    for j in range(n):
        if i & (1<<j):
            isOn.append(j+1)

    flag = True
    for j in range(m):
        count = 0
        for v in s[j]:
            if v in isOn:
                count += 1
        if count % 2 != p[j]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[]
for _ in range(m):
    A.append([i-1 for i in list(map(int,input().split()))[1:]])
P=list(map(int,input().split()))
ans=0
for bit in range(1<<n):
    for j in range(m):
        now=0
        for i in A[j]:
            if bit & 1<<i: now+=1
        if now%2!=P[j] : break
        if j==m-1: 
            
            ans+=1


print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[]
for _ in range(m):
    A.append([i-1 for i in list(map(int,input().split()))[1:]])
P=list(map(int,input().split()))
ans=0
for bit in range(1<<n):
    for j in range(m):
        now=0
        for i in A[j]:
            if bit & 1<<i: now+=1
        if now%2!=P[j] : break
        if j==m-1: 
            
            ans+=1


print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
K = []
S = []
for _ in range(M):
    KS = list(map(int,input().split()))
    k = KS.pop(0)
    K.append(k)
    S.append(KS)
P = list(map(int,input().split()))

cnt = 2 ** N
ans = 0

sum = [0] * M

for j in range(M):
    for x in S[j]:
        sum[j] += 2 ** (x - 1)

for i in range(cnt):
    flg = 1
    for j in range(M):
        calc = sum[j] & i
        sum_str = bin(calc)
        div = sum_str.count('1') % 2
        if P[j] == div:
            continue
        else:
            flg = 0
            break
    if flg == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
sw, li = [int(i) for i in input().split(" ")]
sw_lists = []
sw_arr = [1 for _ in range(sw)]
ans = 0

for i in range(li):
    sw_list = []
    sw_list = [int(j) - 1 for j in input().split(" ")][1:]
    sw_lists.append(sw_list)

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

for i in range(2 ** sw):
    ena_sw = [0 for _ in range(sw)]
    ena_nums = []

    for j in (range(sw)):
        if (i >> j) & 1:
            ena_sw[j] = 1
    
    for j in sw_lists:
        ena_num = []
        for k in j:
            ena_num.append(ena_sw[k])
        ena_nums.append(ena_num)
    
    for ena_num,mod in zip(ena_nums, sw_mod):
        if (sum(ena_num) % 2) != mod:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = []
for i in range(m):
  ks = list(map(int,input().split()))
  s.append(ks)
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  flag = True
  for j in range(m):
    count = 0
    for k in range(s[j][0]):
      if i & (1<<(s[j][k+1]-1)): count += 1
    if count%2!=p[j]: flag = False
  if flag==True: ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lamps = []
for i in range(M):
    row = [int(e) for e in input().split()]
    lamps.append(row[1:])
p = [int(e) for e in input().split()]

ans = 0
for i in range(1 << N):
    ok = True
    for j in range(M):
        c = 0
        for id in lamps[j]:
            if (i >> (id - 1)) & 1:
                c += 1
        c %= 2
        if c != p[j]:
            ok = False
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[list(map(int,input().split()))[1:] for m in range(M)]
p=list(map(int,input().split()))
count=0
for bit in range(1<<N):
    flag=True
    for m in range(M):
        on=0
        for n in range(N):
            if (bit>>n)&1 and n+1 in s[m]:
                on+=1
        if on%2!=p[m]:
            flag=False
    if flag:
        count+=1
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[list(map(int,input().split()))[1:] for m in range(M)]
p=list(map(int,input().split()))
count=0
for i in range(1<<N):
    flag=True
    for m in range(M):
        on=0
        for n in range(N):
            if (i>>n)&1 and n+1 in s[m]:
                on+=1
        if on%2!=p[m]:
            flag=False
    if flag:
        count+=1
print(count)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    point=0
    for j in range(m):
        cnt=0
        for k in A[j]:
            if num[k-1]=="1":cnt +=1
        if cnt%2==P[j]:point +=1
    if point==m:ans +=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ss = []
for i in range(m):
    s = list(map(int, input().split()))
    x = 0
    for i in range(1, len(s)):
        x |= 1 << (s[i] - 1)
    ss.append(x)
pp = list(map(int, input().split()))

ans = 0
for x in range(2 ** n):
    non = 0
    for i in range(m):
        a = ss[i] & x
        nb = 0
        while a != 0:
            if a & 1 == 1:
                nb += 1
            a >>= 1
        if nb % 2 == pp[i]:
            non += 1
    if non == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M=map(int, input().split())
#スイッチN,電球M
S=[[0]*N for _ in range(M)]
for i in range(M):
  ks=map(int, input().split())
  for j,s in enumerate(ks):
    if j==0:
      continue
    S[i][s-1]+=1


P=list(map(int, input().split()))
S=np.array(S)
P=np.array(P)
#スイッチにつけtかた 
ans=0
for i in range(2**N):
  now=np.zeros(M)
  for j in range(N):
    if i>>j&1==1:
      #スイッチONの時
      now+=S[:,j]
  #print((now%2).astype(int))
  ans+=int(((now%2)==P).all())
  #print(i,j,now)
#print(P)
print(ans)

Submission status: Accepted

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

q = []
for i in range(m):
    q.append(list(map(int, input().split())))
p = list(map(int, input().split()))


#sのX桁目が1ならX個目のスイッチがON
for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1:
                cnt += 1
        if cnt%2 != p[i]:
            judge = False
    if judge:
        res += 1

print(res)

Submission status: Accepted

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


count = 0
for i in range(2**n):
    for j in range(m):
        swich_on = 0
        for k in range(len(s[j])):
            swich_on += (i >> (s[j][k] - 1)) & 1
        if swich_on % 2 != p[j]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ans = 0
K = [0]*m
S = [0]*m
for i in range(m):
    I = input().split()
    K[i],S[i] = int(I[0]), list(map(int,I[1:]))
P = list(map(int,input().split()))

for i in range(2**n):
    on = [0]*n
    j = 0
    while i > 0:
        if i&1:
            on[j] = 1
        i = i >> 1
        j += 1
    cnt = [0]*m
    flag = 1
    for j in range(m):
        for s in S[j]:
            cnt[j] += on[s-1]
        if (cnt[j]-P[j])&1:
            flag = 0
    ans += flag
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
K = [[0]*N]*M
for i in range(M):
  K[i] = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
total = 0
for i in range(2 ** N):
    lamp = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            lamp[j] = 1
    flag = True
    for x in range(M):
      result = 0
      for y in K[x][1:]:
        if lamp[y-1] == 1:
          result += 1
      result %= 2
      if result != P[x]:
        flag = False
    if flag:
      total += 1
print(total)

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().split()]
ks = []
for _ in range(m):
    ks.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]
ans = 0
for i in range(2**n):
    li = []
    flag = True
    for j in range(n):
        if (i>>j) & 1:
            li.append(1)
        else:
            li.append(0)
    
    for o,j in enumerate(ks):
        cnt = 0
        for l in range(1,j[0]+1):
            if li[j[l]-1]==1:
                cnt+=1
        if cnt%2!=p[o]:
            flag = False
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
K = [[0]*N]*M
for i in range(M):
  K[i] = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
total = 0
for i in range(2 ** N):
    lamp = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            lamp[j] = 1
    flag = True
    for x in range(M):
      result = 0
      for y in K[x][1:]:
        if lamp[y-1] == 1:
          result += 1
      result %= 2
      if result != P[x]:
        flag = False
    if flag:
      total += 1
print(total)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
K = []
S = []
for _ in range(M):
    KS = list(map(int,input().split()))
    k = KS.pop(0)
    K.append(k)
    S.append(KS)
P = list(map(int,input().split()))

cnt = 2 ** N
ans = 0

for i in range(cnt):
    flg = 1
    for j in range(M):
        s = S[j]
        sum_s = 0
        for x in s:
            sum_s += 2 ** (x - 1)
        calc = sum_s & i
        sum_str = bin(calc)
        div = sum_str.count('1') % 2
        if P[j] == div:
            continue
        else:
            flg = 0
            break
    if flg == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

# s[i] := i番目のスイッチについている電球群
s = [[] for _ in range(n)]
for i in range(m):
  temp = [int(i) for i in input().split()]
  k.append(temp[0])
  for j in temp[1:]:
    s[j-1].append(i)

p = [int(i) for i in input().split()]
count = 0
for i in range(2 ** n):
  state = [0 for _ in range(m)]
  for j in range(n):
    # スイッチがついていたら、つながっている電球に+1する
    if (i >> j) & 1:
      for k in s[j]:
        state[k] = (state[k] + 1) % 2
  if state == p:
    count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
count = 0
for i in range(2 ** N):
    for m in range(M):
        switch = 0
        for j in range(N):
            if (i >> j) & 1:
                if j + 1 in s[m]:
                    switch += 1
        if switch % 2 != p[m]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
def main():
    n,m = map(int,input().split())
    S = []
    for _ in range(m):
        s = list(map(int,input().split()))
        s.pop(0)
        S.append(s)
    p = list(map(int,input().split()))
    status = [[0,1] for i in range(n)]
    cnt = 0
    for on in itertools.product(*status):
        flag = 0
        for i in range(m):
            s = 0
            for j in range(len(S[i])):
                if on[S[i][j]-1]==1:
                    s += 1
            if s%2==p[i]:
                flag += 1
                if flag==m:
                    cnt += 1
                continue
            else:
                break
    print(cnt)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
for i in product(range(2), repeat=n):
    for j in range(m):
        total = 0
        for k in ks[j][1:]:
            total += i[k-1]
        if total%2!=p[j]:
            break
    else: ans+=1
    
print(ans)