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:
def ABC106_B():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    ans = 0
    for i in range((N+1)//2):
        cur = i*2+1
        if len(make_divisors(cur))==8:
            ans += 1
    print(ans)
    return

def ABC122_B():
    S = SI()
    ans = 0
    cur = 0
    d = {"A","C","G","T"}
    for s in S:
        if s in d:
            cur += 1
        else:
            ans = max(ans,cur)
            cur = 0
    ans = max(ans,cur)
    print(ans)
    return

def paken2019_C():
    N, M = LI()
    A = [LI()for _ in range(N)]
    T = [i for i in range(M)]
    ans = 0
    for t1,t2 in itertools.permutations(T,2):
        cur = 0
        for i in range(N):
            cur += max(A[i][t1],A[i][t2])
        ans = max(ans,cur)
    print(ans)
    return

def ABC95_C():
    A, B, C, X, Y = LI()
    if A+B<=C*2:
        ans = A*X+B*Y
    else:
        if X>Y:
            ans = Y*C*2 + min(A,C*2)*(X-Y)
        else:
            ans = X*C*2 + min(B,C*2)*(Y-X)
    print(ans)
    return

def SMTB_D():
    def flag(n,s):
        for l in range(n,N):
            if S[l]==str(s):
                return l
        return N
    N = I()
    S = SI()
    ans = 0
    for i in range(10):
        L1 = flag(0,i)
        for j in range(10):
            L2 = flag(L1+1,j)
            for k in range(10):
                L3 = flag(L2+1,k)
                if L3<N:
                    ans += 1
                    #print(i,j,k)
    print(ans)
    return

def JOI2007_3():
    N = I()
    V = [LI() for _ in range(N)]
    D = set()
    for vx,vy in V:
        D.add((vx,vy))
    ans = 0
    for i in range(N):
        a1, b1 = V[i]
        for j in range(i+1,N):
            a2, b2 = V[j]
            va, vb = a2 - a1, b2 - b1
            if (a1 + vb, b1 - va) in D and (a2 + vb, b2 - va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
            if (a1 - vb, b1 + va) in D and (a2 - vb, b2 + va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
    print(ans)
    return
"""
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
"""# 10

def square869120Contest():
    def length(a,b,x,y):
        if x>y:
            x,y = y,x
        rep = 0
        if a<x:
            rep += (x-a)*2
        if y<b:
            rep += (b-y)*2
        rep += (y-x)
        return rep
    N = I()
    AB = [LI()for _ in range(N)]
    ans = inf
    for i in range(N):
        s = AB[i][0]
        for j in range(N):
            g = AB[j][1]
            cur = 0
            for k in range(N):
                cur += length(AB[k][0],AB[k][1],s,g)
            ans = min(ans,cur)
    print(ans)
    return

def JOI7_D():
    M = I()
    S = [LI()for _ in range(M)]
    Ss = [(0,0)]
    curx,cury = S[0]
    for sx,sy in S[1:]:
        Ss.append((sx-curx,sy-cury))
        curx = sx; cury = sy
    #print(Ss)
    N = I()
    X = [LI()for _ in range(N)]
    D = set()
    for i in range(N):
        cur = (X[i][0],X[i][1])
        D.add(cur)
    for i in range(N):
        flag = True
        curx, cury = X[i]
        for k in range(M):
            curx += Ss[k][0]
            cury += Ss[k][1]
            #print(curx,cury)
            if not (curx, cury) in D:
                flag = False
                break
        if flag:
            #print(i,X[i])
            ansx = X[i][0] - S[0][0]
            ansy = X[i][1] - S[0][1]
            print(ansx,ansy)
            return
    return

def ABC128_C():
    N, M = LI()
    S = [[]for _ in range(N)]
    for i in range(M):
        s = LI()
        for j in s[1:]:
            S[j-1].append(i)
    P = LI()
    #print(S)
    loop = 2**N
    ans = 0
    for i in range(loop):
        p = [0]*M
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j)
        for k in cur:
            for l in S[k]:
                p[l] += 1
        flag = True
        for j in range(M):
            if p[j]%2!=P[j]:
                flag = False
        if flag:
            ans += 1
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC128_C()

"""

"""

Submission status: Accepted

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

ans = 0
for bit in range(1<<n):
    on_e = 0
    sw = bin(bit)[2:].zfill(n)
    for i in range(m):
        on_cnt = 0
        for j in range(lst[i][0]):
            if sw[lst[i][j+1]-1] == '1':
                on_cnt += 1
        else:
            if on_cnt % 2 != p[i]:
                continue
            else:
                on_e +=1
    else:
        if on_e == m:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
box = []
for _ in range(m):
    denki = list(map(int,input().split()))
    box.append(denki)
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    flag = 0
    for u in range(m):
        now_box = box[u]
        now_box = now_box[1:]
        cnt = 0
        for j in range(n):
            if ((i>>j)&1) and (j+1) in now_box:
                cnt += 1
        if cnt%2 == p[u]:
            pass
        else:
            flag = 1
            break
    if flag == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
s = [-1]*N
for i in range(2**N):
    for j in range(N):
        if (i >> j) & 1:
            s[j] = 1
        else:
            s[j] = 0
k = [None]*M
si = [None]*M
for i in range(M):
    tmp = list(map(int,input().split()))
    k[i] = tmp[0]
    si[i] = tmp[1:]
p = list(map(int,input().split()))

s = [-1]*N
ans = 0
for i in range(2**N):
    for j in range(N):
        if (i >> j) & 1:
            s[j] = 1
        else:
            s[j] = 0
    f = True
    for x in range(M):
        tmp = sum([1 for y in si[x] if s[y-1]==1]) % 2
        if tmp != p[x]:
            f = False
            break
    if f:
        ans += 1
print(ans)

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 bit in range(1 << N):
    for m in range(M):
        if p[m] != ([bin(bit)[2:].zfill(N)[s-1] for s in S[m]].count('1') % 2):
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ss = []
for _ in range(m):
    _s = (int(x) - 1 for x in input().split())
    next(_s)
    ss.append(set(_s))

*ps, = map(int, input().split())

ret = 0
for bit in range(1 << n):
    cnts = [0] * m
    for sw_id in range(n):
        if (bit >> sw_id) & 1:
            for light_id, _s in enumerate(ss):
                if sw_id in _s:
                    cnts[light_id] += 1
    if all(p == cnt % 2 for p, cnt in zip(ps, cnts)):
        ret += 1
print(ret)

Submission status: Accepted

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

def get_bit(i,n):
  res = []
  for _ in range(n):
    res.append(i%2)
    i = int(i/2)
  return res[::-1]

ans = 0
for i in range(2**n):
  flags = get_bit(i,n)
  for j in range(m):
    count = 0
    for k in ss[j]:
      count += flags[k-1]
    if count %2 == ps[j]:
      continue
    else:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    # state[i]: スイッチiがon
    state = [False] * N
    for j in range(N):
        if 1 & (i >> j):
            state[j] = True
    
    # 全ての電球が点灯するか判定
    flag = True
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if state[s-1]:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = False
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    cond = []
    flag = True
    for j in range(n):
        if (i >> j) & 1 == 1:
            cond.append(1)
        else:
            cond.append(0)
    for j in range(len(connect_l)):
        num_on = 0
        for s in connect_l[j]:
            num_on += cond[s-1]
        if not num_on % 2 == p_l[j]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

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

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


ans = 0
for i in range(2**N):
	flg = [0 for _ in range(M)]
	for j in range(N):
		if i & (1 << j):
			for k in range(M):
				if j+1 in S[k]:
					flg[k] += 1

	cond = 1
	for l in range(M):
		if P[l] != (flg[l] % 2):
			cond = 0
			break

	if cond:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
onof = []
for i in range(m):
    lst1 = list(map(int,input().split()))
    lst1 = lst1[1:]
    onof.append(tuple(lst1))

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

#ビット全探索
def bit_search(lst):
    keta = len(lst)
    bit_lst = []
    for i in range(2**keta):
        sub = []
        for j in range(keta):
            if ((i>>j) &1):
                sub.append(lst[j])
        bit_lst.append(sub)

    return bit_lst

bit_lst = []
for i in range(1,n+1):
    bit_lst.append(i)

bit_lst = bit_search(bit_lst)

ans = 0
for i in bit_lst:
    flag = 1
    for j in range(m): #m個の電球について
        res = 0
        for k in onof[j]: #それぞれのbitについて
            if k in i:
                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())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
res = 0

for i in range(2**n):
    ptn = format(i, 'b').rjust(n, '0')
    light = True
    for j in range(m):
        tmp = 0
        for k in range(1, s[j][0]+1):
            if ptn[s[j][k] - 1] == '1':
                tmp += 1
        if tmp%2 != p[j]:
            light = False
    if light:
        res += 1
print(res)

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    cnt = 0
    for j in range(M):
        tmp = 0
        for s in S[j]:
            if (i & (1<<(s-1))):
                tmp = 1 - tmp
        if tmp % 2 == P[j]:
            cnt += 1
    if cnt ==  M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:



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 = list(map(int, input().split()))
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        on_cnt = 0
        for s in S[i]:
            if bit & (1 << (s-1)):
                on_cnt += 1

        if on_cnt % 2 == P[i]:
            cnt += 1
        
    if cnt == 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()))

sw = [i + 1 for i in range(n)]

t_on = []
for i in range(2 ** n):
    on = []
    for j in range(n):
        if (i>>j) & 1:
            on.append(sw[j])

    t_on.append(on)

ans = 0
for i in range(len(t_on)):
    for j in range(m):
        c = set(t_on[i]) & set(ks[j][1:])
        # print(ks[j][1:], t_on[i], c, len(c), p[j])
        if len(c) % 2 != p[j]: break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

N, M = [int(x) for x in input().split()]
k = []
s = []
for _ in range(M):
    tmp = [int(x) for x in input().split()]
    k.append(tmp[0])
    s.append(tmp[1:])
p = [int(x) for x in input().split()]

ans = 0

for i in range(2 ** N):
    flag = 1
    for j in range(M):
        cnt = 0
        for k in s[j]:
            cnt += (i >> (k - 1)) & 1
        if cnt % 2 != p[j]:
            flag = 0
            break
    ans += flag

print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    s=[0]*M
    for i in range(M):
        li=list(map(int,input().split()))
        s[i]=set(li[1:])
    p=list(map(int,input().split()))
    

    count=0
    for i in range(1<<N):
        flag=True
        output=set()
        for j in range(N):
            if(i>>j)&1:
                output.add(j+1)
        for j in range(M):
            if len(output&s[j])%2!=p[j]:
                flag=False
            if flag==False:
                break
        if flag:
            count+=1
    
    print(count)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
B = [tuple(map(int,input().split())) for _ in range(M)]
P = tuple(map(int,input().split()))

ans = 0

for i in range(2**N):
    flag = True
    for k in range(M):
        on = 0
        
        for j in range(B[k][0]):
            if i>>(B[k][j+1]-1) & 1:
                on += 1
        
        if on%2 != P[k]:
            flag = False
            
    if flag:
        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)]
p=list(map(int,input().split()))
c=0
for _ in range(2**n):
  s=str(bin(_))[2:].zfill(n)
  f=1
  for i in range(m):
    a=0
    for j in range(1,k[i][0]+1):
      a+=int(s[k[i][j]-1])
    if a%2!=p[i]:
      f=0
      break
  if f:
    c+=1
print(c)

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()))
c=0
for _ in range(2**n):
  s=format(_,'0{}b'.format(n))
  f=1
  for i in range(m):
    a=0
    for j in range(1,k[i][0]+1):
      a+=int(s[k[i][j]-1])
    if a%2!=p[i]:
      f=0
      break
  if f:
    c+=1
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=[[] for i in range(m)]
for i in range(m):
  X[i]=list(map(int,input().split()))
  X[i].pop(0)
S=[[] for i in range(n)]
for i in range(m):
  for j in range(len(X[i])):
    S[X[i][j]-1].append(i)
ans=0
P=list(map(int,input().split()))
for i in range(2**n):
  p=[0]*m
  s=format(i, '10b')
  for j in range(n):
    if s[-j-1]=="1":
      for k in range(len(S[j])):
        p[S[j][k]]=(p[S[j][k]]+1)%2
  if p==P:
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s_lst = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    del s_lst[i][0]
p_lst = list(map(int,input().split()))
answer = 0

for i in range(2**n): #各電球がonかoffかビット全探索
    on_lst =[0]*n
    flag = True
    for j in range(n):
        if (i>>j) & 1:
            on_lst[j] = 1
    for l in range(m): ##　一つ一つの電球について確認
        number = 0
        s = s_lst[l]
        for sw in s:
            if on_lst[sw-1]==1:
                number += 1
        if number%2 != p_lst[l]:
            flag = False
            break
    if flag:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K_S = []
for m in range(M):
    k_s = list(map(int, input().split()))
    K_S.append(k_s)
P = list(map(int, input().split()))

result = 0
for switch_pattern in range(2 ** N):
    light_up = True
    for i, k_s in enumerate(K_S):
        count = 0
        for s in k_s[1:]:
            if (switch_pattern >> (s - 1)) & 1:
                count += 1
        # print(f"count: {count}")
        if count % 2 != P[i]:
            light_up = False
            break
    if light_up:
        result += 1
print(result)

# O: 1024*10*10 = 10**5

Submission status: Accepted

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

ans = 0
for b in range(1<<N):
    for i,s in enumerate(S):
        c = 0
        for t in s:
            if b&(1<<(t-1)): c+=1
        if c%2!=P[i]: break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
for i in range(0,M):
    K=list(map(int,input().split()))
    S.append(K[1:])
P=list(map(int,input().split()))
import itertools as it
ans=0
for i in it.product([0,1], repeat=N):
    ON=True
    for s in S:
        cnt=0
        for j in range(0, len(s)):
            if i[s[j]-1]==1:
                cnt+=1
        if cnt%2!=P[S.index(s)]:
            ON=False
    if ON:
        ans+=1
print(ans)

Submission status: Accepted

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

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

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


switches = [[] for i in range(n)]
for idx, light in enumerate(lights):
    for i in range(n):
        if i + 1 in light[1:]:
            switches[i].append(idx)


def sw(nom):
    ret = []
    for i in range(11):
        if nom >> i & 1 == 1:
            ret.append(i)
    return ret


ans = 0
for i in range(1 << n):
    swNoms = sw(i)
    pp = [0 for i in range(m)]
    for swNom in swNoms:
        for lightNom in switches[swNom]:
            pp[lightNom] += 1
    if p == list(map(lambda x: x % 2, pp)):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

n, m = [int(i) for i in input().split()]

#switch[a][b] a番のスイッチがb番の電球とつながっているなら1
switch = [[0]*(m+1) for i in range(n+1)]

for i in range(1,m+1):
    s = [int(j) for j in input().split()]
    del(s[0])

    for j in s:
        switch[j][i] = 1

p = [0] + [int(i) for i in input().split()]

count = 0

for bit in range(1 << n):
    sc = deepcopy(p)
    for i in range(n):
        if bit >> i & 1:
            for j in range(1,m+1):
                sc[j] += switch[i+1][j]

    if all([k % 2 == 0 for k in sc]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  p=tuple(map(int,input().split()))
  
  q=set(sum(li,[]))
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      for u,w in zip(li,p):
        s=set(s)
        if len(s&set(u))%2!=w:
          break
      else:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  p=tuple(map(int,input().split()))
  
  q=set(sum(li,[]))
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      s=set(s)
      t=all(len(s&set(u))%2==w for u,w in zip(li,p))
      if t==True:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  p=tuple(map(int,input().split()))
  
  q=set(sum(li,[]))
  
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      s=set(s)
      for j,t in enumerate(li):
        u=s&set(t)
        if len(u)%2==p[j]:
          continue
        else:
          break
      else:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  li=[set(x) for x in li]
  p=tuple(map(int,input().split()))
  
  q=set()
  for x in li:
    q|=x
  
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      s=set(s)
      for j,t in enumerate(li):
        u=s&t
        if len(u)%2==p[j]:
          continue
        else:
          break
      else:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  li=[set(x) for x in li]
  p=list(map(int,input().split()))
  
  q=set()
  for x in li:
    q|=x
  
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      s=set(s)
      for j,t in enumerate(li):
        u=s&t
        if len(u)%2==p[j]:
          continue
        else:
          break
      else:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
pattern=[]
ans=0
for i in range(M):
    s=list(map(int,input().split()))
    del s[0]
    pattern.append(s)
p=list(map(int,input().split()))
for i in range(2**N):
    tentou=[]
    for j in range(N):
        if ((i>>j)&1):
            tentou.append(j+1)
    for index,f in enumerate(pattern):
        cnt=0
        for g in f:
            if g in tentou:
                cnt+=1
        hantei=cnt%2
        if hantei==p[index]:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:


def main():
    n,m = map(int,input().split())
    
    sw = [ 0 for _ in range(m)]
    for i in range(m):
        _,*sl = map(int,input().split())
        for s in sl:
            sw[i] += 2 ** (s-1)
    p = list(map(int,input().split()))

    b = 0
    ans = 0
    while b < 2**n:
        ok = True
        for i in range(m):
            sc = 0
            for j in range(n):
                bit = int(2 ** (j))
                if (bit & b != 0):
                    continue
                if sw[i] & bit != 0:
                    sc += 1
            #print(sc)
            if sc % 2 != p[i]:
                ok = False
                continue
        if (ok):
            ans += 1
        b += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

pl=list(map(int,input().split()))
ans=0
#中身を扱いやすいように加工する
kl=[]
sl=[]
for i in range(m):
    templ=l[i]
    k=templ[0]
    kl.append(k)
    sl.append(templ[1:k+1])

for i in range(2**n):
    #b=bin(i)
    pt=[0 for l in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            pt[j]=1
    flag=True#全ての電球が点灯するか
    for l in range(m):#1つの電球についてチェック
        count=0
        k=kl[l]
        s=sl[l]
        for sw in s:
            if pt[sw-1]==1:
                count+=1
        if count%2!=pl[l]:
            flag=False
            break
    if flag:
        ans+=1
    
print(ans)

Submission status: Accepted

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

for i in range(M):
    del mat[i][0]

for i in range(2 ** N):
    sw2 = str(format(i, 'b'))
    if len(sw2) < N:
        sw2 = '0' * (N-len(sw2)) + sw2
    lumpcnt = 0
    for lump in range(M):
        on = 0
        for swno in mat[lump]:
            if sw2[swno-1] == '1':
                on += 1
        if on % 2 == p[lump]:
            lumpcnt += 1
    if lumpcnt == M:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[] #全kについて、スイッチの状態を格納する。s[][]で呼び出し
for i in range(m):
	switch=[] #各kについて、スイッチの状態を一旦格納する
	k,*switch=map(int,input().split())
	#switch[i]はswitchの番号であり[1,n]なので、インデックスを1つずつ減らす
	for i in range(k):
		switch[i]-=1
	s.append(switch)
p=list(map(int,input().split()))

ans=0
#スイッチの2**n通りの状態に対して
for state in range(2**n):
	state=list(map(int,format(state,'b').zfill(n)))
	allon=1
	for i in range(m):
		count=0
		for j in range(len(s[i])):
			count+=state[s[i][j]]
		if count%2!=p[i]:
			allon=0
			break
	if allon==1:
		ans+=1
print(ans)

Submission status: Accepted

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

patterns = []
for i in range(2**n):
    patterns.append(list(bin(i)[2:].zfill(n)))

ans = 0

for pattern in patterns:
    on = []
    light = 0
    for j in range(n):
        if pattern[j] == '1':
            on.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in on:
                count += 1
        if count % 2 == p[k]:
            light += 1
    if light == m:
        ans += 1
            
print(ans)

Submission status: Accepted

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

pattern = []
for i in range(2**n):
    pattern.append(list(bin(i)[2:].zfill(n)))

ans = 0

for i in pattern:
    turn = []
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = []
switch = []
for i in range(n):
    switch.append(i+1)
for i in range(m):
    ks = list(map(int,input().split()))
    ls.append(ks)
p = list(map(int,input().split()))


pattern = []
for i in range(2**n):
    pattern.append(list(bin(i)[2:].zfill(n)))

ans = 0

for i in pattern:
    turn = []
    count = 0
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                #print(ls[k][l])
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
        #print(i,turn)
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
d = {}
for i in range(M):
    k, *s, = map(int, input().split())
    d[i] = s
    
*p, = map(int, input().split())

ans = 0
for k in product(range(2), repeat=N):
    a = 0
    for i, m in d.items():
        v = 0
        for j in m:
            v += k[j-1]
        if v%2 == p[i]:
            a += 1
    if a==M:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(m):
    si = list(map(int, input().split()))
    k = si.pop(0)
    ki.append(k)
    smi.append(si)

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

for i in range(2**n):
    h = [0]*n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1
    for j in range(m):
        num = 0
        si = smi[j]
        k = ki[j]
        for l in range(k):
            if h[si[l]-1] == 1:
                num += 1
        if num % 2 != p[j]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=list(map(int,input().split()))
L=[list(map(int,input().split()))[1:] for i in range(m)]
P=list(map(int,input().split()))
cnt=0

for i in range(1<<n):
  k=1
  for p,ll in zip(P,L):
    k*=(sum([int(bin(i)[2:].zfill(n)[l-1]) for l in ll])%2==p)
  cnt+=k
print(cnt)