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:
import itertools
n,m = map(int, input().split())
g = []
for _ in range(m):
  s = list(map(int, input().split()))
  g.append(s[1:])
p = list(map(int, input().split()))
num = 0
for i in list(itertools.product([0,1], repeat=n)):
  a = 0
  for j,k in enumerate(g):
    cnt = 0
    for l in k:
      cnt += i[l-1]
    if cnt%2==p[j]:
      a += 1
  if a == m:
    num+=1
print(num)

Submission status: Accepted

Solution code:
import itertools
N,M = list(map(int,input().split()))
k_lis = []
for i in range(M):
    k_lis.append(list(map(int,input().split())))
P = list(map(int,input().split()))
switch_list = list(itertools.product('01',repeat = N))
ans = 0
sub = 0

for sl in range(len(switch_list)):#スイッチ全探索
    #if  '1' in  (switch_list[sl]):#スイッチが少なくとも一つ点灯
    if True:
        flag = 0
        for i in range(M):#電球１つ１つを探索していく
            counter = 0
            for j in range(1,k_lis[i][0]+1):
                if switch_list[sl][k_lis[i][j]-1] == '1' :
                    counter += 1
                    
            if counter %2 != P[i]:
                flag = 1
                break
        if flag == 0:    
            ans += 1
print(ans)

Submission status: Accepted

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

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for k, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[k]:
      break
  else:
    output += 1
print(output)

Submission status: Accepted

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

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for inde, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[inde]:
      break
  else:
    output += 1
print(output)

Submission status: Accepted

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

bag = []
for n in range(2**N):
    bag_ = []
    for n_ in range(N):
        bag_.append((n >> n_)&1)
    bag.append(bag_)

def get_ON_list(b):
    ON_list=[]
    for m in range(M):
        S_on=0
        for s in S[m]:
            S_on += b[s-1]

        ON_list.append(S_on%2)
    return ON_list

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

ans=0
for b in bag:
    ON_list=get_ON_list(b)
    ans_=1
    for on_idx,on in enumerate(ON_list):
        p=P[on_idx]
        if on != p:
            ans_=0
            break
    ans += ans_
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
switch_list=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    result=[0]*m
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
              if j+1 in switch_list[k][1:]:
                  result[k]+=1
    for l in range(m):
        if (result[l]%2)!=p[l]:
            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 bit in range(1<<N):
    count = [0]*M
    for i in range(N):
        if (bit >> i) & 1:
            for a in range(M):
                if i+1 in ks[a][1:]:
                    count[a] +=1
    a = 0
    for i in range(M):
        if count[i] % 2 == p[i]:
            a += 1
            if a == M:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list1=[]
for i in range (M):
    a=list(map(int,input().split()))
    list1.append(a)
P=list(map(int,input().split()))
switch=[0]*N
count=0
for i in range (2**N):
    switch=[0]*N
    ans=0
    for j in range (N):
        if ((i>>j)&1):
            switch[N-1-j]=1
    for l in range(1,M+1):
        con=0
        for k in range(1,len(list1[l-1])):
            con+=switch[list1[l-1][k]-1]
        if con%2!=P[l-1]:
            ans=1
    if ans==0:
        count+=1

print(count)

Submission status: Accepted

Solution code:
#　解説確認後AC
#　参考ブログ「けんちょんの競プロ精進記録」
#　URL https://drken1215.hatenablog.com/entry/2019/06/15/135300

N,M = map(int,input().split())
s = []
for i in range(M):
    s.append(list(map(int,input().split()))) # 各電球に繋がっているスイッチを格納
    s[i].pop(0) # 先頭要素はスイッチの数なので削除
p = list(map(int,input().split()))

res = 0

for bit in range(1<<N): # bit全探索 O(2**N)
    ok = True
    for i in range(M):
        con = 0
        for v in s[i]: # i個目の電球に繋がっているスイッチの数だけループ
            if bit & (1<<(v-1)): con += 1 # スイッチvがONならカウント+1
        if con % 2 != p[i]: ok = False # 電球が点灯する条件になっているか
    if ok: res += 1 # 電球が全て点灯しているならカウント+1
print(res)

Submission status: Accepted

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

res = 0

for bit in range(1<<N):
    ok = True
    for i in range(M):
        con = 0
        for v in s[i]:
            if bit & (1<<(v-1)): con += 1
        if con % 2 != p[i]: ok = False
    if ok: res += 1
print(res)

Submission status: Accepted

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

switchMap = []
for i in range(N):
    switchMap.append([])
for i, s in enumerate(S):
    for ss in s:
        switchMap[ss-1].append(i)

count = 0
for i in range(pow(2, N)):
    switches = bin(i).replace("0b", "").zfill(N)
    light = [0] * M
    for j, switch in enumerate(switches):
        if switch == '1':
            for s in switchMap[j]:
                light[s] += 1

    flag = True
    for j, l in enumerate(light):
        if l % 2 != P[j]:
            flag = False
            break

    if flag:
        # print(switches)
        count += 1

print(count)

Submission status: Accepted

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

    for i in range(2**N):
        tmp_comb = set()
        for j in range(N):
            if (i >> j) & 1:
                tmp_comb.add(j+1)
        switch_combs.append(tmp_comb)
    num_sum = 0

    for comb in switch_combs:
        for i in range(len(lights)):
            num_match = len(lights[i] & comb)
            if not num_match % 2 == P[i]:
                break
        else:
            num_sum += 1
    print(num_sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

n,m = map(int, input().split())
ks = []
for _ in range(m):
    sl = list(map(int, input().split()))
    ks.append(sl[1:])

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


ans = 0
pattern = 2
ite = product(range(pattern),repeat=n)
for it in ite:
    s_on_off = list(it)
    for bulb, p in zip(ks, pl):
        curr_cnt = 0
        for s in bulb:
            if s_on_off[s-1] == 1: curr_cnt+=1
        if curr_cnt%2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
s = defaultdict(list)

for i in range(1, m + 1):
    _, *x = map(int, input().split())
    for j in x:
        s[j].append(i)

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


ans = []
for i in range(2**n):
    tmp = [0] * len(p)
    for j in range(n):
        if ((i >> j) & 1):
            for k in s[j + 1]:
                tmp[k - 1] += 1
    if all([x % 2 == y for x, y in zip(tmp, p)]):
        ans.append(True)
    else:
        ans.append(False)

print(sum(ans))

Submission status: Accepted

Solution code:
from itertools import product

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

count = 0
for S in product((0, 1), repeat=n):
  if all(sum(S[s - 1] for s in ks[1:]) % 2 == p for p, ks in zip(P, KS)):
    count += 1
print(count)

Submission status: Accepted

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k_m, s_m = l[0], l[1:]
        k.append(k_m)
        s.append(s_m)
    p = list(map(int, input().split()))

    return N, M, k, s, p


def lights_on(M: int, s: list, p: list, switches: int) -> bool:
    """
    電球がすべて点灯しているかどうかを確認する.

    Args:\n
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
        switches (int): スイッチの状態

    Returns:\n
        bool: 電球がすべて点灯していれば真、そうでなければ偽
    """
    result = True
    for m in range(M):
        switch_on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                switch_on_count += 1
        if switch_on_count % 2 != p[m]:
            result = False

    return result


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
    """
    # 求解処理
    ans = 0
    for switches in range(1 << N):
        if lights_on(M, s, p, switches):
            ans += 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, k, s, p = get_input()

    # メイン処理
    main(N, M, s, p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k_m, s_m = l[0], l[1:]
        k.append(k_m)
        s.append(s_m)
    p = list(map(int, input().split()))

    return N, M, k, s, p


def lights_on(M: int, s: list, p: list, switches: int) -> bool:
    """
    電球がすべて点灯しているかどうかを確認する.

    Args:\n
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
        switches (int): スイッチの状態

    Returns:\n
        bool: 電球がすべて点灯していれば真、そうでなければ偽
    """
    result = True
    for m in range(M):
        switch_on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                switch_on_count += 1
        if switch_on_count % 2 != p[m]:
            result = False

    return result


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
    """
    # 求解処理
    ans = 0
    for switches in range(1 << N):
        if lights_on(M, s, p, switches):
            ans += 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, k, s, p = get_input()

    # メイン処理
    main(N, M, s, p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, M = list(map(int, input().split()))
k, s = [], []
for m in range(M):
    l = list(map(int, input().split()))
    k_m, s_m = l[0], l[1:]
    k.append(k_m)
    s.append(s_m)
p = list(map(int, input().split()))


def lights_on(switches: int) -> bool:
    result = True
    for m in range(M):
        on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                on_count += 1
        if on_count % 2 != p[m]:
            result = False

    return result


# 求解処理
ans = 0
for switches in range(1 << N):
    if lights_on(switches):
        ans += 1

# 結果出力
print(ans)

Submission status: Accepted

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

wiring = []
for i in range(m):
    k, *s = map(int, input().split())
    
    for j in range(k):
        s[j] -= 1
    
    wiring.append(s)

p_i = [int(x) for x in input().split()]

ans = 0
for i in range(2**n):
    swiches = [-1] * n
    lamps = [0] * m
    for j in range(n):
        swiches[j] = (i >> j) & 1
        
    for j in range(m):
        cnt = 0
        for w in wiring[j]:
            if swiches[w] == 1:
                cnt += 1
        
        if cnt % 2 == p_i[j]:
            lamps[j] = 1
    
    if sum(lamps) == 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()))
cnt = 0

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

Submission status: Accepted

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

sm=0
for x in range(2**n):
    onlst=[0 for _ in range(m)]
    for i in range(n):
        if x>>i&1:
            for j in range(m):
                if i+1 in swi[j] :
                    onlst[j]+=1
    if [x%2 for x in onlst]==res : sm+=1
print(sm)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(m)]
p = [int(i) for i in input().split()]
c = 0
for sw in product((0, 1), repeat=n):
    for i in range(m):
        if sum(sw[si - 1] for si in l[i][1:]) % 2 != p[i]:
            break
    else:
        c += 1
print(c)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
ks = [[int(i) for i in input().split()] for _ in range(m)]
p = [int(i) for i in input().split()]
cnt = 0
for i in range(2**n):
  on = set(j + 1 for j in range(n) if i >> j & 1 == 1)
  flag = True
  for j in range(m):
    _, *s = ks[j]
    flag &= len(on & set(s)) % 2 == p[j]
  cnt += flag
print(cnt)

Submission status: Accepted

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

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


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:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
lamp=[]
for _ in range(m):
    lamp_i=list(map(int,input().split()))
    lamp.append(lamp_i[1:])
p=list(map(int,input().split()))
ans=0
for bit in itertools.product([0,1],repeat=n):
    f=True
    for i in range(m):
        s_i=sum(bit[s-1] for s in lamp[i])
        if (s_i-p[i])%2!=0:
            f=False
            break
    if f:
        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()))
a=0
for bit in range(1<<n):
 for j in range(m):
  c=0
  for k in s[j][1:]:
   if bit&(1<<(k-1)):c+=1
  if c%2!=p[j]:break
 else:a+=1
print(a)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    flag = True
    for j in range(m):
        c = 0
        for v in s[j]:
            if i >> (v-1) & 1:
                c += 1
        if c%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,m=f()
S=[f()[1:] for _ in [0]*m]
p=f()
print(sum(all(sum(i>>~-k for k in S[j])%2==p[j] for j in range(m)) for i in range(2**n)))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
S=[[0]*n for _ in [0]*m]
for i in range(m):
  _,*s=f()
  for j in s: S[i][j-1]=1
p=[*f()]
print(sum(all(sum(i>>j&1*S[k][j] for j in range(n))%2==p[k] for k in range(m)) for i in range(2**n)))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
S=[[0]*n for _ in range(m)]
for i in range(m):
  _,*s=f()
  for j in s: S[i][j-1]=1
p=[*f()]
a=0
for i in range(2**n):
  if all(sum(S[k][j] for j in range(n) if i>>j&1)%2==p[k] for k in range(m)): a+=1
print(a)

Submission status: Accepted

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

for i in range(M):
    ks = list(map(int, input().split()))
    K[i] = ks[0]
    S[i] = ks[1:]
P = list(map(int, input().split()))


n = N
Switch = [[] for _ in range(n+1)]
ans = 0
for bit in range(2**n):
    cost = 0
    for i in range(n):
        mask = 1 << i
        if bit & mask:
            Switch[i+1] = 1
        else:
            Switch[i+1] = 0
#    print()
#    print(Switch)
    
    Light = [0 for _ in range(M)]
    for i in range(M):
        count = 0
        for s in S[i]:
            count += Switch[s]
#        print(count)
        if count%2 == P[i]:
            Light[i] = 1
#    print(Light)
    if all(Light):
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    state = [0] * n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            state[j] = 1
    for k in range(m):
        c = 0
        for l in li[k]:
            c += state[l-1]
        if c%2 != p[k]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lst=[]
for i in range(m):
    a=[int(x) for x in input().split()]
    a=[x-1 for x in a]
    lst.append(a[1:])
p=[int(x) for x in input().split()]
ans=0

for i in range(2**n):
    on=[]
    light_on=0
    for j in range(n):
        if ((i>>j)&1):
            on.append(j)
    for j in range(m):
        num_on=0
        for k in range(len(lst[j])):
            if lst[j][k] in on:
                num_on+=1
        if (num_on%2)==p[j]:
            light_on+=1
    if light_on==m:
        ans+=1

print(ans)

Submission status: Accepted

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

ans = 0

for bit in range(1<<n):
  on = 0
  for i in range(m):
    numon = 0
    k = k_s[i][0]
    s = k_s[i][1:]
    for j in range(k):
      mask = 1<<(s[j]-1)
      if mask&bit:
        numon += 1
    if numon%2 == p[i]:
      on += 1
  if on == m:
    ans += 1

print(ans)

Submission status: Accepted

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

index = [i for i in range(1, n+1)]
counter = 0

for i in range(2**n):
  cand_list = []
  flg = True
  
  for j in range(n):
    if i&1<<j:
      cand_list.append(index[j])
  
  for k_i, k in enumerate(K):
    if len(set(cand_list)&set(k))%2!=P[k_i]:
      flg = False
      break
  if flg:
    counter += 1
    
print(counter)

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

switch = [0]*N

res = 0
for i in range(1<<N):
    div = i
    for j in range(N):
        switch[j] = div % 2
        div //= 2

    on = True
    for l in range(M):
        s_state = 0
        for s_check in s[l]:
            s_state ^= switch[s_check-1]
        if s_state != p[l]:
            on = False
    
    if on:
        res += 1

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product

def judge(co,m,k,s,p):
    flag = True
    for i in range(m):
        _s = s[i]
        _p = p[i]
        _k = k[i]
        amount = sum([co[_s[j]-1] for j in range(_k)])
        if amount % 2 != _p:
            flag = False
    return flag 



def solve(n,m,k,s,p):
    b = product((0,1),repeat=n)
    c = 0
    for co in b:
        if judge(co,m,k,s,p):
            c += 1
    return c



def main():
    N,M = map(int,input().split())
    k = []
    s = []
    for _ in range(M):
        tmp = list(map(int,input().split()))
        k.append(tmp[0])
        s.append(tmp[1:])
    p = list(map(int,input().split()))
    print(solve(N,M,k,s,p))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k , s = [], []
for m in range(M):
  line = list(map(int, input().split()))
  k.append(line[0])
  s.append(line[1:])
p = list(map(int, input().split()))
light_up = [0] * M
ans = 0

for bit in range(0, 1<<N):
  bit_str = format(bit, 'b').zfill(N)
  for m in range(M):
    counter = 0
    for index in s[m]:
      counter += int(bit_str[index-1])
    if counter%2 == p[m]:
      light_up[m] = 1
    else:
      light_up[m] = 0
  if sum(light_up) == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
n,m = map(int,input().split())
card =[[0]*n for _ in range(m)]
for i in range(m):
    switch = list(map(int,input().split()))[1:]
    for k in switch:
        card[i][k-1] = 1
##どこに繋がっているかを配列で表現

#print(card)


ans =list(map(int,input().split()))
cnt=0
from itertools import combinations
##全通りを調べる
for epoch in range(1,n+1):
    
    for j in combinations(range(1,n+1),epoch):
        sco =[]
        for lisa in card:##一つずつの照明について調べる
            score =0
            for l in j:
                score += lisa[l-1]
                
            sco.append(score)
        #print(sco)
        if list(np.array(sco)%2) == ans:
            cnt+=1
    

if ans == [0]*m:
    cnt+=1
        
print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import product
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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 pattern in product([0, 1], repeat=n):
        total = 0
        for i in range(m):
            cnt = 0
            for idx, p in enumerate(pattern):
                if p == 1 and idx + 1 in S[i][1:]:
                    cnt += 1
            if cnt % 2 == P[i]:
                total += 1
        if total == m:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def dfs(A):
    global cnt

    if len(A) == n:
        ans = [0 for i in range(m)]
        for i, a in enumerate(A):
            if a:
                for j in range(m):
                    if i+1 in s[j]:
                        ans[j] += 1
        for x, y in zip(p, ans):
            if x != y%2:
                break
        else:
            cnt += 1
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

n, m = map(int, input().split())
s = [list(map(int, sys.stdin.readline().split()))[1:]  for x in range(m)]
p = list(map(int, sys.stdin.readline().split()))
cnt = 0
dfs([])
print(cnt)

Submission status: Accepted

Solution code:
def dfs(A):
    global cnt

    if len(A) == n:
        ans = [0 for i in range(m)]
        for i, a in enumerate(A):
            if a:
                for j in range(m):
                    if i+1 in s[j]:
                        ans[j] += 1
        for x, y in zip(p, ans):
            if x != y%2:
                break
        else:
            cnt += 1
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:]  for _ in range(m)]
p = list(map(int, input().split()))
cnt = 0
dfs([])
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
k = [0 for _ in range(m)]
s = [[] for _ in range(m)]
for i in range(m):
  k[i],*s[i] = map(lambda x:int(x)-1,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(m):
  ds = ["0"]*n
  for j in s[i]:
    ds[j] = "1"
  s[i] = int("".join(ds),2)
for i in range(2**n):
  for j in range(m):
    if not bin(i&s[j]).count("1")%2 == p[j]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

S = []
for i in range(m):
    s = list(map(int, input().split()))
    S.append(s[1:])
    
P = [int(i) for i in input().split()]
    
A = [0, 1]
ans = 0
for a in itertools.product(A, repeat = n):
    flag = 0
    for j in range(m):
        cnt = 0
        for s in S[j]:
            if a[s - 1] == 1:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch_list = []
for _ in range(m):
  tmp = list(map(int, input().split()))
  switch_list.append(tmp[1:])
p_list = list(map(int, input().split()))

all_on_cnt = 0

for i in range(2**n):
  light_list = [0 for _ in range(m)]
  on_off = [0 for _ in range(n)]
  
  cnt = 0
  while i!=0:
    on_off[cnt] = i%2
    i//=2
    cnt+=1
  
  for j in range(m):
    tmp = switch_list[j]
    on_cnt = 0
    for k in tmp:
      on_cnt += on_off[k-1]
    if on_cnt%2==p_list[j]:
      light_list[j]=1
  if sum(light_list)==m:
    all_on_cnt+=1
print(all_on_cnt)

Submission status: Accepted

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

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

output = 0
for index in range(2 ** n):

    light = 0
    for mm in range(m):
        count = 0
        for shift in switches[mm]:
            if (index >> shift - 1) & 1:
                count += 1
        if count % 2 == passes[mm]:
            light += 1
    
    if light == m:
        output += 1

print(output)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
K = [0]*M
S = [None]*M
for j in range(M):
    lis = list(map(int, input().split()))
    K[j] = lis.pop(0)
    S[j] = lis
    
P = list(map(int, input().split()))

count = 0
for b in range(2**N):
    onoff = [b>>i & 1 for i in range(N)]
    flag = True
    for m in range(M):
        slist = S[m]
        ON = 0
        for s in slist:
            ON += onoff[s-1]
        if ON % 2 != P[m]:
            flag = False
            break
    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sw=[[] for _ in range(m)]
for _ in range(m):
    temp=list(map(int,input().split()))
    sw[_]=temp[1:]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for l,s in enumerate(sw):
        cnt=0
        for k in s:
            if temp[k-1]==1: cnt+=1
        if p[l]!=cnt%2:
            flag=0
            break
    if flag: ans+=1
print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for l,s in enumerate(sw):
        cnt=0
        for k in s:
            if temp[k-1]==1: cnt+=1
        if p[l]!=cnt%2:
            flag=0
            break
    if flag: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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 itertools.product(range(2), repeat=N):
    cnt = [0 for _ in range(M)]  # 各電球のスイッチがオンになっている数
    for c, k in enumerate(KS):  # 電球Kが関係しているスイッチを調べる
        for j in k[1:]:
            j -= 1
            if i[j] == 1:
                cnt[c] += 1

    for m, c in enumerate(cnt):
        if c % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]
S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]


def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)
    for light_idx in range(num_of_lights):
        # print(f"switch_idx = {switch_idx}, light_idx = {light_idx}")
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    # print(f"switch_idx = {switch_idx}: not choose = {lights}, choose = {_lights} ")
    switch_on_result = rec(switch_idx + 1, _lights)
    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)