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())
S = [[]for i in range(M)]
for i in range(M):
    k_s = list(map(int, input().split()))
    for j in range(len(k_s)-1):
        S[i].append(k_s[j+1])
p = list(map(int, input().split()))
Answer = 0
#print(S)

for i in range(2 ** N):
    switch = [0]*N
    for j in range(N):  # このループが一番のポイント
        a = 0
        if ((i >> j) & 1):
            a = 1

        switch[j] = a


    flag = True
    for j in range(M):
        Sum = 0
        for k in range(len(S[j])):
            #print(j,k)
            Sum += switch[S[j][k]-1]

        if (Sum%2) != p[j]:
            break

        if j == M-1:
            Answer += 1

print(Answer)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
denkyu_switch=[]
res=0
for i in range(m):
    denkyu_switch+=[list(map(int, input().split()))[1:]]
p=list(map(int, input().split()))
for i in range(2**n):
    denkyu = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in denkyu_switch[k]:
                    denkyu[k]+=1
    denkyu2=[i%2 for i in denkyu]
    if p==denkyu2:
        res+=1
print(res)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k_i=[]
S=[]
for i in range(M):
  l = list(map(int,input().split()))
  k_i.append(l[0])
  S.append(l[1:])
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
  flag=1
  for j in range(M):
    res=0
    for k,x in enumerate(bin(i)[2:][::-1]):
      if x=="1" and k+1 in S[j]:
        res+=1
    if res%2 != P[j] :
      flag=0
      break
    
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ls=[]
cnt,cnt2,ans=0,0,0
for i in range(M):
    ls1=list(map(int,input().split()))
    ls.append(list(ls1))
    ls1.clear()
lsp = list(map(int,input().split()))
#print(ls)
#print(lsp)
for i in range(2**N):
    flg = True
    for j in range(M):
        cnt = 0
        for k in range(1,len(ls[j])):
            if i >> ls[j][k]-1 & 1:
                cnt += 1
        if cnt%2 != lsp[j]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M=map(int,input().split())
ary_list = []
for i in range(M):
    S = list(map(int,input().split()))
    S.pop(0)
    ary_list.append(S)
P_list = list(map(int,input().split()))
check = True
count = 0
swith = np.array([False]*N)
for i in range(2**N):
    for j in range(N):
        if ((i>>j)&1):
            swith[j] = True
        else:
            swith[j] = False
    for k,p in zip(ary_list,P_list):
        if(list(swith[np.array(k)-1]).count(True)%2!=p):
            check = False
    if(check):
        count+=1
    check=True
print(count)

Submission status: Accepted

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

ans = 0

for x in range(2**N):                                                                             
    ok = True                                                                                                          
    for si in range(M):                                                                           
        cnt = 0
        for s in S[si]:                                                                           
            if x & (1 << (s - 1)):                                                                                     
                cnt += 1
        if cnt % 2 != P[si]:                                                                                           
            ok = False                                                                            
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
n,m=map(int,input().split())
k=[]
for i in range(m):
    s=list(map(int,input().split()))
    s = list(map( lambda x:x-1,s))
    k.append(s[1:])
p=list(map(int,input().split()))

ans=0

for bit in range(1<<n):
    cnt_swit=[0]*m
    for i in range(n):
        if bit>>i & 1:
            for j in range(m):
                if i in k[j]:
                    cnt_swit[j]+=1
    cnt_swit = list(map( lambda x:x%2,cnt_swit))
    tmp=0
    for pi,cnt in zip(p,cnt_swit):
        if pi==cnt:
            tmp+=1
    if tmp==m:
        ans+=1
print(ans)

Submission status: Accepted

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

#すべてのonoffの組み合わせについてbit全探索
for i in range(2**n):
    on_lamp = 0 #転倒したランプの個数をカウント
    #すべてのランプについて
    for j in range(m):
        on_sw = 0 #スイッチがonの個数をカウント
        for k in range(n):
            #スイッチがonかつランプにつながっていたらインクリメント
            if (i >> k) & 1 and k in lamp_list[j]:
                on_sw += 1
        if on_sw%2 == p[j]:
            on_lamp += 1
    if on_lamp == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for _ in range(m):
  k,*b=map(int,input().split())
  s.append(b)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  tr=bin(i)[2:].zfill(n)
  light=0
  for j in range(m):
    sw=0
    for l in s[j]:
      if tr[l-1]=='1':
        sw+=1
    if sw%2==p[j]:
      light+=1
  if light==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
connected = []  # 二次元リスト
for _ in range(M):
    # それぞれの行の1つ目の入力は、その後に続く値の個数
    connected.append(list(map(int, input().split())))
mod = list(map(int, input().split()))
ans = 0

for is_on_li in product([False, True], repeat=N):
    is_ok = True
    for light_idx in range(M):
        on_cnt = 0
        for i in range(1, len(connected[light_idx])):
            sw_idx = connected[light_idx][i] - 1
            if is_on_li[sw_idx]:
                on_cnt += 1
        if on_cnt % 2 != mod[light_idx]:
            is_ok = False
    if is_ok:
        ans += 1
print(ans)

Submission status: Accepted

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

switch = []


for _ in range(M):
    s = input().split()
    switch.append(s)
p = input().split()

#print(switch)
#print(p)
ans = 0
for i in range(1<<N):
    s = []
    for j in range(N):
        if (i>>j)&1 == 1:
            s.append(1)
        else:
            s.append(0)
    #print(s)
    
    cnt = 0
    for k in range(M):
        #cnt = 0
        a = 0
        for l in range(int(switch[k][0])):
            a += s[int(switch[k][l+1])-1]
        #print(a)
        #print(a%2)
        
        if a % 2 == int(p[k]):
            cnt += 1
        
    if cnt == M:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m = LI()
bulbs = []
for _ in range(m):
    b = LI()
    bulbs.append(b[1:])
p = LI()
ans = 0


for switch in range(1 << n):
    check = [0]*m
    for i, bulb in enumerate(bulbs):
        cnt = 0
        for b in bulb:
            if (switch>>(b-1))&1:
                cnt+=1
        if cnt % 2 == p[i]:
            check[i] = True
        else:
            check[i] = False
    if all(check):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N,M = map(int,input().split())
cc = []
for i in range(M):
  ll = list(map(int,input().split()))
  cc.append(ll)
p = list(map(int,input().split()))
count = 0
for i in product([0,1],repeat = N):
  bulb = []
  for j in range(M):
    on = 0
    for k in range(cc[j][0]):
      if i[cc[j][k+1]-1] == 1:
        on += 1
    if on % 2 == p[j]:
      bulb.append(1)
  if sum(bulb) == M:
    count += 1

print(count)

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
s=[]

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

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

for i in range(2**n):
    x=format(i,'010b')
    #print(x)
    flg=1
    for j in range(m):
        temp=0
        for k in range(1,s[j][0]+1):
            temp+=int(x[-s[j][k]])
        if temp % 2 != p[j]:
            flg=0
            break
    if flg:
        ans+=1


print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
# スイッチがn個
# 電球がm個
k = []
for i in range(m):
    k.append(list(map(int, input().split())))
p = list(map(int, input().split()))

count = 0

for i in product([0,1], repeat=n):
    switch = []
    for j in range(m):
        on = 0
        for l in range(k[j][0]):
            if i[k[j][l+1]-1] == 1:
                on += 1
        if on % 2 == p[j]:
            switch.append(1)
    if sum(switch) == m:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    words = list(map(int, input().split()))
    k.append(words[0])
    s.append(words[1:])
p = tuple(map(int, input().split()))

sw_stat_list = list(itertools.product([0, 1], repeat=n))
for i in range(m):
    sw_stat_list_next = []
    for sw_stat in sw_stat_list:
        sw_on_num = sum([sw_stat[sw - 1] for sw in s[i]])
        if sw_on_num % 2 == p[i]:
            sw_stat_list_next.append(sw_stat)
    sw_stat_list = sw_stat_list_next

print(len(sw_stat_list))

Submission status: Accepted

Solution code:
def main():
    ans = 0
    n,m = map(int,input().split())
    s = []
    for i in range(m):
        tmp = [int(i) for i in input().split()]
        s.append(tmp)
    p = [int(i) for i in input().split()]
    for i in range(2**n):
        light = [0 for k in range(m)]
        for j in range(n):
            if (i>>j)&1 == 1:
                for x in range(m):
                    if j+1 in s[x][1:s[x][0]+1]:
                        light[x] += 1
        Flag = True
        for x in range(m):
            """
            if light[x]==0:
                Flag = False
                """
            if light[x]%2!=p[x]:
                Flag = False
        if Flag:
            ans += 1

    print(ans)

main()

Submission status: Accepted

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

Submission status: Accepted

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

count = 0
for i in range(2 ** N):#1024
  on = [0] * N
  ans = [0] * M
  ans2 = [1] * M
  for j in range(N):#10
    if ((i >> j) & 1):
      on[j] = 1
  #print(on)
  for k in range(M):#10
    now = 0
    for l in K[k]:
      if on[l - 1] == 1:
        now += 1
    if now % 2 == P[k]:
      ans[k] = 1
  #print(on, ans)
  if ans == ans2:
    count += 1

print(count)

Submission status: Accepted

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

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

import itertools 
data = list(itertools.product(range(2), repeat = n))
ans = 0

for d in data:
    light = 0
    for i in range(m):
        s_cnt = 0
        for j in range(k[i]):
            s_no = s[i][j]-1
            if d[s_no]==1: s_cnt+=1
        if s_cnt%2==p[i]:
            light += 1
    if light == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

N, M = nm()
K = []
S = []
for _ in range(M):
    tmp = nl()
    K.append(tmp[0])
    S.append(tmp[1:])
P = nl()
ans = 0
for state in range(1 << N):
    isOn = [True if (state >> i) % 2 == 1 else False for i in range(N)]
    isOK = True
    for i, li in enumerate(S):
        sum = 0
        for s in li:
            if isOn[s-1]:
                sum += 1
        if not sum % 2 == P[i]:
            isOK = False
            break
    if isOK:
        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()))
cnt = 0
for i in range(2**n):
    switch = [0]*n
    
    f = True
    for k in range(n):
        if(i>>k)&1:
            switch[k] = 1
    #print(switch)
    for j in range(m):
        sum = 0
        for k in range(len(s[j])):
            if switch[s[j][k]-1] == 1:
                sum += 1
        if sum % 2 != p[j]:
            f = False
    if f:
        cnt += 1
        



print(cnt)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
Con = [[] for I in range(0,M)]
for T in range(0,M): Con[T] = [int(x) for x in input().split()][1:]
Lights = [int(x) for x in input().split()]
Count = 0
for TT in range(0,pow(2,N)):
    Flag = True
    Switch = list(int(x) for x in list(('{:0'+str(N)+'b}').format(TT,'b')))
    for T in range(0,M):
        if sum(Switch[x-1] for x in Con[T])%2!=Lights[T]:
            Flag = False
            break
    if Flag: Count += 1
print(Count)

Submission status: Accepted

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

for _ in range(M):
    f = list(map(int, input().split()))
    k = f[0]
    s = f[1:]
    K.append(k)
    S.append([c-1 for c in s])

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

search = 1<<N
ans = 0
for i in range(search):
    b = [0]*N
    for j in range(N):
        if i & 1<<j:
            b[j] = 1
        else:
            b[j] = 0

    ok = True
    for q in range(M):
        n = 0
        for s in S[q]:
            n += b[s]
    
        if n%2 != P[q]:
            ok = False
            break
    
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(m)]
k2=[]
for v in k:
  a=[2**(v[i]-1) for i in range(1,v[0]+1)]
  k2.append(sum(a))
  
p=list(map(int,input().split()))

sm=0
for i in range(2**n):
  c=1
  for j in range(m):
    b=bin(k2[j] &i)
    
    d=b.count("1")
    if d%2!=p[j]:
      c=0
  if c==1:
    sm+=1

print(sm)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
K = [0]*m
S = [[] for _ in range(m)]    

for i in range(m):
    K[i], *S[i] = map(int, input().split())
P = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    s = list(map(int, list(bin(i)[2:].zfill(n))))
    for j in range(m):
        p = [_s for k,_s in enumerate(s) if k+1 in S[j]]
        if sum(p)%2!=P[j]:
            break
        else:
            if j==m-1:
                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):
    onoff = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in ks[k][1:]:
                    onoff[k] +=1
    cnt = 0
    for l in range(m):
        if onoff[l] % 2 == p[l]:
            cnt += 1
        if cnt == m:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = [LIST() for i in range(m)]
p = LIST()
ans = 0

for i in range(2**n):
    sw = []
    for j in range(n):
        sw.append(( i >> j ) & 1)
    for j in range(m):
        reg = 0    
        for k in range(1, s[j][0]+1):
            reg += sw[s[j][k]-1]
        if reg % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N, M = MI()
K, switch = [], []

for _ in range(M):
    k, *s = MI()
    K.append(k)
    switch.append(s)
    
p = LI()
ans = 0

for i in range(1 << N):
    on = [False] * N
    
    for j in range(N):
        if (i >> j) & 1:
            on[j] = True
    
    can = True
    
    for k in range(M):
        tmp = 0
        for s in switch[k]:
            tmp += on[s - 1]
            
        if tmp % 2 != p[k]:
            can = False
            break
    
    ans += can
    
print(ans)

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, M = iInM()
KS = iInLD(M)
P = iInLH()

ans = 0
for i in range(2**N):
    isOn = [False] * N
    for j in range(N):
        isOn[N-1-j] = ((i >> j) & 1) == 1
    for j in range(M):
        cnt = 0
        for k in range(KS[j][0]):
            cnt += isOn[KS[j][k+1]-1]
        if cnt % 2 != P[j]:
            break
    else:
        ans += 1
    #print(isOn, cnt)

print(ans)

Submission status: Accepted

Solution code:

import itertools
N, M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
   
for i in itertools.product([0,1], repeat=N):
    dame = 0
    for j in range(M):
        temp = p[j]
        for k in s[j][1::]:
            temp += i[k-1]
        if temp%2:
            dame = 1
    if not dame:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(list(map(int, input().split()))[1:] for i in range(M)) #改行行列
    ps = tuple(map(int, input().split()))
    #print(S)
    ans=0
    for i in range(2**N):
        cnt=0
        for j in range(M):
            p=ps[j]
            tot=0
            for s in S[j]:
                tot^=((i>>(s-1))&1)
            if tot==p:
                cnt+=1
        if cnt==M:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product


def main():
    n, m = map(int, input().split())
    s = np.full((m, n), False, dtype=bool)

    for i in range(m):
        line = list(map(int, input().split()))
        for e in line[1:]:
            s[i][e-1] = True

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

    ans = 0

    for pat in product((False, True), repeat=n):
        for i in range(m):
            if np.sum(np.logical_and(s[i], pat)) % 2 != p[i]:
                break
        else:
            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()))

a = 0
for bit in range(1 << N):
    flag = True
    for i in range(M):
        c = 0
        for j in K[i][1:]:
            if bit & (1 << (j - 1)):
                c += 1
        if c % 2 != P[i]:
            flag = False
            break
    if flag:
        a += 1

print(a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
e = [[*map(int, input().split())][1:] for _ in range(m)]
p = [*map(int, input().split())]

c = 0

for i in range(2**n):
    count = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if j + 1 in e[k]:
                    count[k] = (count[k] + 1) % 2
    if count == p:
        c += 1
print(c)

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()))
  
ans = 0
for b in range(2 ** n):
  onswitch = [i + 1 for i in range(n) if (b >> i) & 1]
  if all(sum(o in s for o in onswitch) % 2 == p for s, p in zip(S, P)):
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
# N switches, M bulbs
N,M = map(int,input().split())
K = []
for i in range(M):
  lst = list(map(int,input().split()))
  K.append([i-1 for i in lst[1:] ])

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

for i in range(1<<N):
  on = []
  for j in range(N):
    if (i>>j)&1:
      on.append(j)

  flg = True
  for m in range(M):
    k = K[m]
    tmp = 0
    for s in k:
      if s in on:
        tmp += 1
    p = P[m]
    if tmp % 2 != p:
      flg = False
      break

  if flg:
    res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int, input().split())
switches = []
for _ in range(m):
    k, *s = map(lambda x: int(x)-1, input().split())
    switches.append(s)
p = list(map(int, input().split()))

ans = 0
for subset in product((0, 1), repeat=n):
    for j in range(m):
        on_cnt = sum(subset[s] for s in switches[j])
        if on_cnt % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
N, M = map(int, input().split())
lights = []
for m in range(M):
    tmp = list(map(int, input().split()))
    lights.append(tmp[1:])
    
    
 
 
P = list(map(int, input().split()))
 
ans = 0
for product in list(itertools.product([0, 1], repeat=N)):
    for light in range(len(lights)):
        cnt = 0
        for l in lights[light]:
            cnt += product[l-1]
        if cnt % 2 != P[light]:
            break
        if light == len(lights) - 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
answer = 0
li = []
for i in range(m):
    li.append(list(map(int,input().split())))
li1 = list(map(int,input().split()))
for i in range(2**n):
    b = "0"*(n-len(bin(i))+2)+bin(i)[2:]
    libi = [int(b[s]) for s in range(n)]
    c = 0
    for j in range(m):
        c1 = 0
        for k in range(li[j][0]):
            if libi[li[j][k+1]-1] == 1:
                c1 += 1
        if c1 % 2 == li1[j]:
            c += 1
    if c == m:
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
import itertools

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


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

ans = 0
for product in list(itertools.product([0, 1], repeat=N)):
    for light in range(len(lights)):
        cnt = 0
        for l in lights[light]:
            cnt += product[l-1]
        if cnt % 2 != P[light]:
            break
        if light == len(lights) - 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 11

n, m = map(int, input().split())
ks_l = [[int(x) for x in input().split()] for y in range(m)]
p_l = [int(x) for x in input().split()]

ans = 0

for i in range(2**n):
    for j in range(m):
        _tmp = 0
        for k in range(ks_l[j][0]):
            if((i >> (ks_l[j][k+1] - 1)) & 1):
                _tmp += 1
        if (_tmp % 2) != p_l[j]:
            break
    else:
        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_or_off = [0]*M
  for j in range(N):
    if (i>>j)&1:
      for k in range(M):
        if j+1 in ks[k][1:]:
          on_or_off[k] += 1
  cnt = 0
  for l in range(M):
    if on_or_off[l]%2 == P[l]:
      cnt += 1
  if cnt == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
K = []
S = []
for _ in range(m):
    k, *s = map(int, input().split())
    K.append(k)
    S.append(s)
P = list(map(int, input().split()))

def ok_by_switch_state(ONs):
    for i in range(m):
        on_cnt = 0
        for s in S[i]:
            s -= 1
            on_cnt += (ONs & 1<<s) != 0
        if on_cnt % 2 != P[i]:
            return False
    else:
        return True
ans = 0
for i in range(2 ** n):
    ans += ok_by_switch_state(i)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1:] for _ in range(M)]

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

ret = 0
for p in product([0,1], repeat=N):
    f = True
    for i in range(M):
        c = 0
        for s in S[i]:
            c += p[s-1]
        if c%2 != P[i]:
            f = False
    if f: ret += 1

print(ret)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
klist = []
swlist = []
ans = 0
for s in range(m):
	k,*sw = list(map(int,input().split()))#kとswを別々に入力
	klist.append(k) #<- kのリスト
	swlist.append(sw) #<- swのリスト
pwlist = list(map(int,input().split())) #pwのリスト

for i in range(2**n):#0~2**nまでの整数をカウントする(整数→ビットでの全探索)
	check = True
	for lump in range(m):#m個の電球についてカウントする
		cnt = 0
		for j in range(klist[lump]):#各スイッチ内の右シフト数をカウント	
			if (i>>swlist[lump][j]-1)&1==1:#右にjシフトする
				cnt += 1#整数iのビットに対し、klistのスイッチがいくつonかをカウントする
		if cnt%2 != pwlist[lump]:#一つのスイッチ列でのカウント終了につき、判定する
			check = False#pwと互換性が1つでもなければFalseとする
	if check == True:#最後までFalseにならなければ組み合わせがあるということになる
		ans += 1
print(ans)