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 resolve():
    import itertools
    N, M = map(int, input().split())
    S = []
    K = []
    ans = 0
    for _ in range(M):
        s = list(map(int, input().split()))
        K.append(s[0])
        S.append(s[1:])
    P = list(map(int, input().split()))
    for i in itertools.product([0,1], repeat=N):
        count = 0
        for j in range(M):
            ichi = 0
            for q in range(K[j]):
                ichi += i[S[j][q]-1]
            if ichi%2 == P[j]:
                count += 1
        if count == M:
            ans += 1
    print(ans)
resolve()

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    # pattern
    flg = True
    for p in range(m):
        cnt = 0
        for j in range(n):
            # 右シフト
            if (i >> j) & 1:
                if (j + 1) in switches[p][1:]:
                    cnt += 1
        if cnt % 2 != correct[p]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n,m = map(int,input().split())
    lt = []
    for i in range(m):
        lt.append(list(map(int,input().split())))
    p = list(map(int,input().split()))
    stats = ((0,1) for i in range(n))
    ans = 0
    for stat in itertools.product(*stats):
        flg = 0
        for i in range(m):
            cnt = 0
            for j in range(1,lt[i][0]+1):
                if stat[lt[i][j]-1]==1:
                    cnt+=1
            if cnt%2!=p[i]:
                flg = 1
                break
        if flg==0:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
b = '0' + str(n) + 'b'
for i in range(1 << n):
    sw = format(i,b)
    if all(sum(sw[g-1] == '1' for g in s[j])%2 == p[j] for j in range(m)):
        ans += 1
print(ans)

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()))
cnt = 0
for a in range(2 ** N):
    flag = 1
    for i in range(M):
        if sum([(a >> (x - 1)) & 1 for x in s[i]]) % 2 != p[i]:
            flag = 0
            break
    cnt += flag
print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Connect = [0] * M
for i in range(M):
    k, *Connect[i] = map(int,input().split())
P = list(map(int,input().split()))
Switch = [0] * N
ans = 0
for i in range(1<<N):
    for j in range(N):
        bit = i>>j & 1
        Switch[j] = bit
    flag = True
    for l in range(M):
        count = 0
        for c in Connect[l]:
            if Switch[c-1]:
                count+=1
        if not P[l] == count % 2:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1  & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2  & 0x3333333333333333)
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4  & 0x0f0f0f0f0f0f0f0f)
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8  & 0x00ff00ff00ff00ff)
    x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff)
    x = (x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff)
    return x

n, m = map(int, input().split())

mask = []
for i in range(m):
    vals = list(map(int, input().split()))
    bits = 0
    for s in vals[1:]:
        bits |= 1 << (s-1)
    mask.append(bits)
p = list(map(int, input().split()))

cnt = 0
for i in range(1 << n):
    if all([popcount(i & mask[j]) % 2 ^ p[j] == 0 for j in range(m)]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
K = []
for i in range(M):
	ks = rl()
	K.append(ks[1:])
P = rl()

def check(b):
	for i in range(M):
		if sum([b[k-1] for k in K[i]]) % 2 != P[i]:
			return False
	return True

cnt = 0
for b in product([0, 1], repeat=N):
	if check(b):
		cnt += 1
print(cnt)

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 i in range(2**n):
    t=0
    for j in range(m):
        o=sum(1 for h in k[j][1:] if i >>(h-1)&1)
        if o%2==p[j]:
            t+=1
    if t==m:
        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,=map(int,input().split())
print(sum(1for i in range(2**N) if M==sum(1for j in range(M) if sum(1for h in k[j][1:] if i>>(h-1)&1)%2==p[j])))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)] 
*p,=map(int,input().split())
t=0
a=0
for i in range(2 ** N):
 t=sum(1 for j in range(M) if sum(1 for h in k[j][1:] if i>>(h-1)&1)%2==p[j])
 if t==M:a+=1
print(a)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)] 
*p,=map(int,input().split())
t=0
a=0
for i in range(2 ** N):
 t=0
 for j in range(M):
  if sum(1 for h in k[j][1:] if i>>(h-1)&1)%2==p[j]:t+=1
 if t==M:a+=1
print(a)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)] 
*p,=map(int,input().split())
t=0
a=0
for i in range(2 ** N): # 点灯しているスイッチ
    t=0
    for j in range(M): # それぞれの電球
        #print(k[j][0],k[j][1:],p[j])
        o=sum(1 for h in k[j][1:] if i>>(h-1)&1) # onしているスイッチの個数
        #print('{:05b}'.format(i),j+1,o)
        if o%2==p[j]:
            t+=1
    if t==M:
        a+=1
print(a)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
xs=[list(map(int,input().split()))[1:] for i in range(m)]
p=tuple(map(int,input().split()))
ans=0
for switch in itertools.product(range(2),repeat=n):
  judge=True
  for i in range(m):
    cnt=0
    lst=xs[i]
    for j in lst:
      cnt+=switch[j-1]
    if cnt%2!=p[i]:
      judge=False
      break
  if judge:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]
    n, m = [int(x) for x in input().split()]
    s = []
    for _ in range(m):
        k, *r = [int(x) - 1 for x in input().split()]
        s.append(r)
    p = [int(x) for x in input().split()]
    ans = 0
    for i in range(2 ** n): # mask
        ok = 1
        for j in range(m): # bulb
            pp = p[j]
            cnt = 0
            for ss in s[j]:
                if i & (1 << ss):
                    cnt += 1
            if cnt % 2 != pp:
                ok = 0
        ans += ok
    print(ans)

    


t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

Solution code:
import itertools
N, M = [int(_) for _ in input().split()]
KS = [[int(_) - 1 for _ in input().split()] for _ in range(M)]
P = [int(_) for _ in input().split()]
ans = 0
for switches in itertools.product(range(2), repeat=N):
    f = all(
        sum(switches[s] for s in ks[1:]) % 2 == P[i]
        for i, ks in enumerate(KS))
    ans += f
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools

import numpy as np


# 読み込み
n, m = map(int, input().split())
swicthes = np.zeros((m, n), dtype=int)

for i in range(m):
    _, *s = map(lambda x: int(x) - 1, input().split())
    swicthes[i, np.array(s, dtype=int)] = 1

l = list(map(int, input().split()))
p = np.array(l, dtype=int)

# bit全探索
count = 0
for on in itertools.product([0, 1], repeat=n):
    _on = np.array(on, dtype=int)
    status = np.sum(swicthes * _on, axis=1) % 2
    if np.sum(p == status) == m:
        # 全ての電球が点灯している
        count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n, m = map(int, input().split())

lamps = [list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))

ans = 0

for i in range(1 << n):
    for r in range(m):
        on_sum=0
        for j in range(n):
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1

        if on_sum % 2 != p[r]:
            break

    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
N, M = list(map(int, input().split()))
q = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))

result_count = 0
for i in range(2**N):
    flag = True
    for idx, j in enumerate(q):  # 電球の数分ループ
        tmp_count = 0
        for k in j[1:]:
            if i >> (k - 1) & 1 == 1:
                tmp_count += 1
        if tmp_count % 2 != p[idx]:
            flag = False
    result_count += 1 if flag else 0

print(result_count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
q = [list(map(int, input().split())) for i in range(m)]
p= list(map(int, input().split()))
ans = 0
 
for s in range(2**n): #スイッチのon/offの状態の総当たり（2**n通り）
    judge = True
    for i in range(m): #電球1つずつに対して
        cnt=0
        for j in range(1,len(q[i])): #sの総当たりでqに当てはまるものを探す。kはforを1からにすれば無視できる。
            w=q[i][j]
            if s >> (w-1) &1 ==1: #sをw-1回シフトさせて(w-1)個目のスイッチがonか判定
                cnt+=1 #onになっているスイッチの個数をカウント
        if cnt % 2 != p[i]: #スイッチの個数を2で割った余りがpiに等しいか判定
            judge = False
    if judge:
        ans += 1
 
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if (i>>j&1):
            l[j]=1
    on=0
    for k in range(m):
        cnt=0
        for o in range(1,len(light[k])):
            if (l[light[k][o]-1]==1):
                cnt+=1
        if cnt%2==p[k]:
            on+=1
    if on==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ls3 = []
for i in range(M):
    ls1=list(map(int,input().split()))
    ls1.pop(0)
    ls3.append(ls1)
ls2 = list(map(int,input().split()))

kk = 0
for i in range(2**N):
    ls4 = [0]*M
    for j in range(N):
        if (i>>j&1):
            for k in range(M):
                if j+1 in ls3[k]:
                    ls4[k] += 1
    ii = 0
    for l in range(M):
        if ls4[l] % 2==ls2[l]:
            ii += 1

    if ii == M:
        kk += 1
print(kk)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = []
for m in range(M):
    s = list(map(int, input().split()))
    S.append(s[1:])
    
p = list(map(int, input().split()))

ans = 0
for c in product([0, 1], repeat = N):
    ok = True
    for m in range(M):
        sm = 0
        for k in S[m]:
            sm += c[k - 1]
        if sm % 2 != p[m]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M = map(int,input().split())
    switches = []
    for i in range(M):
        switches.append(list(map(int,input().split()))[1:])
    P = list(map(int,input().split()))
    ans = 0
    for i in range(2**N):
        on = [False]*N
        for j in range(N):
            if (2**j) & i :
                on[j] = True

        for j in range(M):
            count = 0
            for s in switches[j]:
                if on[s-1]:
                    count += 1
            if count % 2 != P[j]:
                break
            else:
                continue
            break
        else:
            ans += 1
    print(ans)










main()

Submission status: Accepted

Solution code:
import itertools

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

#onにするスイッチを選ぶ
switch = [i for i in range(1,n+1)]
comb = []
for i in range(n+1):
    for v in itertools.combinations(switch,i):
        comb.append(v)

ans = 0
for i in comb:
    for j in range(m):
        tmp = 0
        for l in range(1,ks[j][0]+1):
            if ks[j][l] in i:
                tmp += 1
        if tmp%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k = [0]*m
s = [0]*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(1 << n):
    cnt = [0]*m
    for j in range(n):
        if (i >> j) % 2 == 1:
            for a in range(m):
                if j + 1 in s[a]:
                    cnt[a] += 1
    chk = 0
    for j in range(m):
        if cnt[j] % 2 != p[j]:
            chk = 1
            break
    if chk == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
array = []
for _ in range(M):
    array.append(list(map(int,input().split()))[1:])
P = list(map(int,input().split()))
count = 0
for mask in range(2**N):
    se = set()
    for i in range(N):
        if mask>>i & 1:
            se.add(i+1)
    for m in range(M):
        p = P[m]
        tmp = 0
        for j in array[m]:
            if j in se:
                tmp+=1
        if tmp%2!=p:
            break
    else:
        count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
k = deque()
s = deque()
for _ in range(M):
    inp = list(map(int, input().split()))
    k.append(inp[0])
    s.append(inp[1:])
p = list(map(int, input().split()))

ans = 0
for i in range(1<<N):
  all_on = True
  for m_i in range(M):
    swon = 0
    for s_i in s[m_i]:
      if i>>(s_i-1)&1:
        swon += 1
    
    if swon%2 != p[m_i]: #電球がOFFだったら
      all_on = False
      break
  
  if all_on: ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools
from itertools import product
# from decimal import Decimal
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
k = [list(map(int, readline().split())) for _ in range(m)]
p = list(map(int, readline().split()))

ans = 0
flag = True

for i in product((0, 1), repeat=n):
    #print(i, i[0])

    for j, valK in enumerate(k):
        pp = p[j]
        temp = 0
        for k1, k2 in enumerate(valK):
            if (k1 == 0):
                continue
            else:
                temp += i[k2 - 1]

        if (temp % 2 == pp):
            continue
        else:
            flag = False
            break
    if (flag is False):
        flag = True
        continue
    else:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    swi = []
    for i in range(M):
        k, *ss = list(map(int, input().split()))
        t = 0
        for s in ss:
            t += 1 << (s-1)
        swi.append(t)

    ps = list(map(int, input().split()))
    ans = 0
    for i in range(1 << N):
        for s, p in zip(swi, ps):
            t = i & s
            c = bin(t).count('1') % 2
            if c != p:
                break
        else:
            ans += 1
    print(ans)
    return

resolve()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = [0 for m in range(M)]
count = 0

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

for i in range(2**N):
  op = [0]*N
  for j in range(N):
    if ((i>>j) & 1):
      op[N-1-j] = 1
      
  flag = True
  
  for k in range(M):
    S = 0
    for l in range(K[k][0]):
      S += op[K[k][l+1]-1]
    if S % 2 != P[k]:
      flag = False
  if flag:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools

N, M = list(map(int, input().split(" ")))
k = []
for _ in range(M):
    k.append(list(map(int, input().split(" "))))
p = list(map(int, input().split(" ")))

bits = itertools.product(["on", "off"], repeat=N)

def tento(bit, k, p):
    for i, pi in enumerate(p):
        ki = list(k[i])
        tmp = 0
        for kij in ki[1:]:
            if bit[kij-1] == "on":
                tmp += 1
        if tmp % 2 != pi:
            return False
    return True

res = 0
for bit in bits:
    if tento(bit, k, p):
        res+=1
print(res)

Submission status: Accepted

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

ans=0


for i in range(2**n):
  kara=[]
  check=0
  for j in range(n):
    if (i>>j)&1:
      kara.append(j+1)
  for q in range(m):
    kari=denk[q]
    kyoutuu=set(kari)&set(kara)
    aa=len(kyoutuu)%2
    if aa==amari[q]:
      check+=1
  if check==m:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools


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


def main():
    N, M = map(int, input().split())
    K = [[] for _ in range(M)]

    for j in range(M):
        k = list(map(int, input().split()))
        K[j] = set(k[1:])
    P = list(map(int, input().split()))
    count = 0
    l = list(range(1, N + 1))
    for i in range(0, N + 1):
        for comb in itertools.combinations(l, i):
            flag =0
            for j in range(M):  # denkyu
                temp = set(comb)
                if len(temp.intersection(K[j]) )% 2 != P[j]:
                    flag = 1
                    break
            if flag ==0:
                count +=1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [0] * m
ans = 0
for i in range(m):
    s[i] = list(map(int,input().split()))
    s[i] = s[i][1:]
p = list(map(int,input().split()))
for k in range(2**n):
    a = format(k,'0'+str(n)+'b')
    t = True
    for i in range(m):
        if sum(a[j-1] == '1' for j in s[i])%2 != p[i]:
            t = False
            break
    ans += t
print(ans)

Submission status: Accepted

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

ans = 0
for state in range(2 ** N):
  for m in range(M):
    count = 0
    for s in S[m]:
      if state & (1 << (s - 1)):
        count += 1
    if count % 2 != P[m]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n): #スイッチの状態
    cnt = 0
    for j in range(m): #電球の状態
        s_on = 0
        for k in range(s[j][0]):
            s_on += (i >> (s[j][k+1]-1) & 1)
        if s_on % 2 == p[j]:
            cnt += 1
    if cnt == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
N,M =map(int, input().split())
q = list()

for i in range(M):
  q.append(list(map(int, input().split()))) #q[0]はqのlength
p = list(map(int, input().split())) #スイッチの偶奇正解を示す

ans = 0

for s in range(2**N):  #sは各スイッチ
  judge = True
  for i in range(M):
    cnt = 0
    for j in range(1, len(q[i])): #range(1,x)は2番目から(K+1)-1番目まで
      w = q[i][j] #i番目のスイッチ,j番目の電球
      if s >> (w-1) & 1 == 1: # 右シフト
        cnt += 1
    if cnt % 2 != p[i]:
      judge = False
  if judge:
    ans += 1
print(ans)

Submission status: Accepted

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

switch = []

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


ans = 0
for i in range(2**n):
    s = []
    for j in range(n):
        s.append((i>>j)&1)
    f = 1
    for j in range(m):
        a = 0
        for k in switch[j]:
            a += s[k]

        if a%2== p[j]:
            pass
        else:
            f = 0
            break

    if f:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ks = []
for i in range(M):
  tmp = list(map(int, input().split()))
  ks.append(tmp)
p = list(map(int, input().split()))

total = 0
for i in range(int(2**N)):
  bin_val = bin(i)				# 2進数に変換
  bin_val = str(bin_val[2:])	# 先頭２文字を除外し、文字列に変換
  bin_val = bin_val.zfill(N)	# N桁になるように先頭に0を追加
#  print(bin_val)
  
  flag = 1
  for j in range(M):
    count = 0
    k = ks[j][0]
    s = ks[j][1:k+1]
    for l in range(k):      
      if bin_val[s[l]-1] == '1':
        count += 1
    if count % 2 != p[j]:
      flag = 0
      break
  if flag == 1:
    total += 1
print(total)

Submission status: Accepted

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

ans = 0

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:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
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
B = 1 << N
for i in range(B):
  L = [0] * M
  for j in range(M):
    for k in ks[j][1:]:
      if i >> (k - 1) & 1:
        L[j] = (L[j] + 1) % 2
  for j in range(M):
    if L[j] != p[j]:
      break
  else:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 17:07:34 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  l_s = []
  for i in range(M):
    l_s.append(list(map(int, input().split()))[1:])
  P = list(map(int, input().split()))

  ans = 0
  for bit in range(1 << N):
    # loop for light
    for lidx, ss in enumerate(l_s):

      num_on_s = 0
      for s in ss:
        mask = (1 << (s-1))
        if bit & mask:
          num_on_s += 1
      if num_on_s % 2 == P[lidx]:
        continue
      break
    else:
      ans += 1
  print(ans)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

ans = 0
for state in range(1 << N):
    for m in range(M):
        count = 0
        for s in S[m]:
            if state & (1 << (s - 1)):
                count += 1
        if count % 2 != P[m]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = [list(map(lambda x:int(x)-1, input().split()))[1:] for _ in range(m)]
rest = list(map(int, input().split()))
ans = 0
for bit in range(1<<n):
    for j in range(m):
        on_sum = 0
        for i in range(n):
            if bit >> i & 1 and i in switch[j]:
                on_sum += 1
        if on_sum % 2 != rest[j]:
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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


def on_count(p):
    c = 0
    while p > 0:
        if p % 2 == 1:
            c += 1
        p //= 2
    return c


switches = []
for i in range(M):
    k, *sw = map(int, input().split())
    switches.append(sw)
P = list(map(int, input().split()))

total = 0
for pattern in product([0, 1], repeat=N):
    t = 0
    for k, indices in enumerate(switches):
        n_on = 0
        for idx in indices:
            if pattern[idx-1]:
                n_on += 1
        if n_on % 2 == P[k]:
            t += 1
    if t == M:
        total += 1
print(total)

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()))

ans = 0
for i in range(1 << n):
    light = 0
    for j in range(m):
        cnt = 0
        for k in range(n):
            if i >> k & 1 and (k + 1) in s[j]:
                cnt += 1
        if cnt % 2 == p[j]:
            light += 1
    if light == m:
        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()))
ans = 0
for i in range(1<<N):
    ok = True
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i&(1<<(s-1)):
                cnt += 1
        if cnt%2 != P[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
klst = []
for i in range(m):
  klst.append(list(map(lambda x: int(x) - 1, input().split()))[1:])
plst = list(map(int, input().split()))
res = 0
for ibit in range(2 ** n):
  TF = True
  for j in range(m):
    cnt = 0
    for swnum in klst[j]:
      if ((ibit >> swnum) & 1):
        cnt += 1
    if cnt % 2 != plst[j]:
      TF = False
  if TF:
    res += 1
print(res)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
l = []
for i in range(m):
    a=(list(map(int,input().split())))
    l.append(a[1:])
b = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    sw = [0 for i in range (m)]
    g = i+0
    for j in range(n):
        if g &1 == True:
            for k in range(m):
                if j+1 in l[k]:
                    sw[k]+=1
        g = g>>1
    cnt = 0
    for j in range(m):
        if sw[j]%2==b[j]:
            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 i in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
  onswichi = [False] * n
  onlight = [0] * m
  for j in range(n):
    if (i >> j) & 1:
      onswichi[j] = True
  for k in range(m):
    cnt = 0
    for f in ks[k][1:]:
      if onswichi[f-1]:
        cnt += 1
    if cnt % 2 == p[k]:
      onlight[k] = 1
  if sum(onlight) == m:
    ans += 1
print(ans)

Submission status: Accepted

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

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

#print(L)

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

ans=0

for i in range(2**N):
    sw=[0 for i in range(M)]
    I=i+0
    for j in range(N):
        if I&1==True:
            for k in range(M):
                if j+1 in L[k]:
                    sw[k]+=1
        I=I>>1
    #print(sw)
    cnt=0
    for j in range(M):
        if sw[j]%2==S[j]:
            cnt+=1
    if cnt==M:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m = map(int, input().split())
    S = []
    for i 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 i in range(2**n):
        check = [False]*m
        for j in range(m):
            s = S[j]
            cnt = 0
            for idx in s:
                if (i>>idx)&1:
                    cnt += 1
            if cnt%2 == p[j]:
                check[j] = True
        if not False in check:
            ans += 1
    print(ans)

        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

ans = 0
for x in product([0,1], repeat=n):
    c = True
    for i in range(m):
        count = 0
        for j in range(k[i]):
            if x[s[i][j]-1] == 1:
                count += 1
        if count % 2 != p[i]:
            c = False
            break
    if c:
        ans += 1
print(ans)