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: Wrong Answer

Solution code:
N, M = map(int, input().split())
den_lists = []
for m in range(M):
    den_lists.append(list(map(int, input().split())))
p = list(map(int, input().split()))
#print(p)
count = 0

for i in range(2**N+1):
    s_list = []
    for j in range(N):
        if (i >> j) & 1:
            s_list.append(j)
    #print(f"s_list:{s_list}")     
    den_count = 0
    for m, den in enumerate(den_lists):
        tmp = 0
        for d in den[1:]:
            if d-1 in s_list:
                tmp += 1
        #print(f"tmp:{tmp}")        
        if tmp % 2 == p[m]:
            #print(m)
            den_count += 1
    #print(f"den_count:{den_count}")
        
    if den_count == len(den_lists):
        count += 1
        
    
    

print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
S = []
for _ in range(m):
    k, *s = [int(x) for x in input().split()]
    s = list(map(lambda x: x - 1, s))  # 0-indexed
    S.append(s)

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

for i in range(2 ** n):
    now_s = []
    flag = True
    for j in range(n):
        if (i >> j & 1):
            now_s.append(1)
        else:
            now_s.append(0)
    tmp = 0
    for k in range(m):
        s = S[k]
        for x in s:
            if now_s[x] == 1:
                tmp += now_s[x]
        if tmp % 2 != P[k]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
c=0
for i in range(2**n):
    xi=format(i,'b').zfill(n)
    light_count=0
    for j in range(m):
        xl=[i for i, x in enumerate(xi) if x == '1']
        c1=0
        for k in range(1,len(l[j])):
            if l[j][k] in xl:c1+=1
        if c1%2==p[j]:light_count+=1
    if light_count==m:c+=1
print(c)

Submission status: Wrong Answer

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


k = []
s = []
ans = 0

for i in range(m):
    k_temp, *s_temp = list(map(int, input().split()))
    k.append(k_temp)
    s.append(s_temp)

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

for bit in range(1 << n):
    light_on = 0
    for i in range(m):
        switch_on = 0
        for j in range(k[i]):
            if (bit >> s[i][j]) & 1:
                switch_on += 1

        if switch_on % 2 == p[i]:
            light_on += 1

    if light_on == m:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = 10, 10


k = [4, 3, 4, 5, 6, 5, 4, 4, 4, 4]
s = [[6, 3, 7, 5], [1, 10, 5], [8, 7, 1, 2], [5, 10, 2, 7, 8],
     [3, 1, 6, 8, 2, 5], [6, 10, 7, 1, 3], [3, 5, 7, 6],
     [3, 9, 7, 5], [3, 6, 5, 7], [2, 7, 1, 8]]
ans = 0

# for i in range(m):
#     k_temp, *s_temp = list(map(int, input().split()))
#     k.append(k_temp)
#     s.append(s_temp)

p = [0, 0, 1, 1, 1, 0, 0, 0, 0, 1]

for bit in range(1 << n):
    light_on = 0
    for i in range(m):
        switch_on = 0
        for j in range(k[i]):
            if (bit >> s[i][j]) & 1:
                switch_on += 1

        if switch_on % 2 == p[i]:
            light_on += 1

    if light_on == m:
        ans += 1

print(ans)

Submission status: Wrong Answer

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


k = []
s = []
ans = 0

for i in range(m):
    k_temp, *s_temp = list(map(int, input().split()))
    k.append(k_temp)
    s.append(s_temp)

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

for bit in range(1 << n):
    light_on = 0
    for i in range(m):
        switch_on = 0
        for j in range(k[i]):
            if (bit & s[i][j]) == s[i][j]:
                switch_on += 1
        else:
            if switch_on % 2 == p[i]:
                light_on += 1

    if light_on == m:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(list(map(int, input().split())))
    a[i] = a[i][1:]
p = list(map(int, input().split()))
light = [False] * n
judge = [False] * m
ans = 0
rank = [0] * m
def dfs(step):
    global ans
    if False not in judge:
        ans += 1
    for k in range(step, n):
        light[k] = True
        for j in range(m):
            if k + 1 in a[j]:
                rank[j] ^= 1
                if rank[j] == p[j]:
                    judge[j] = True
                else:
                    judge[j] = False
        dfs(k + 1)
        light[k] = False
dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(list(map(int, input().split())))
    a[i] = a[i][1:]
p = list(map(int, input().split()))
light = [False] * n
judge = [False] * m
ans = 0
rank = [0] * m
def dfs(step):
    global ans
    if False not in judge:
        if step < n:
            ans += 2**(n-step)
        else:
            ans += 1
    for k in range(step, n):
        light[k] = True
        for j in range(m):
            if k + 1 in a[j]:
                rank[j] ^= 1
                if rank[j] == p[j]:
                    judge[j] = True
                else:
                    judge[j] = False
        dfs(k + 1)
        light[k] = False
dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
# できてない。

def main():
    n, m = map(int, input().split())
    # ｋは何個のスイッチにつながっているか、ｓはスイッチの番号
    s = []; k = [] # s : どのスイッチとつながってるか、インデックスは電球を指す、　k: 電球が何個のスイッチとつながっているか
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    # スイッチの状態は２進数表記で表す。スイッチはｎ個あるので
    for bit in range(2**n):
        ok = True
        # スイッチの状態を表すbitを2進数で表したとき1のところがそのスイッチが点灯してることに対応している
        # それをi = 0,...,n-1で探索する
        for i in range(m):
            cnt = 0
            for v in s[i]:
                #このときのiは点灯してるスイッチの番号と同じ
                if bit & (1 << v):
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False

        if ok: # okなら全ての電球が付いているということ
            res += 1

    print(res)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


def main():
    n, m = map(int, input().split())
    # ｋは何個のスイッチにつながっているか、ｓはスイッチの番号
    s = []; k = [] # s : どのスイッチとつながってるか、インデックスは電球を指す、　k: 電球が何個のスイッチとつながっているか
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    # スイッチの状態は２進数表記で表す。スイッチはｎ個あるので
    for bit in range(2**n):
        ok = True
        # スイッチの状態を表すbitを2進数で表したとき1のところがそのスイッチが点灯してることに対応している
        # それをi = 0,...,n-1で探索する
        for i in range(m):
            cnt = 0
            for v in s[i]:
                #このときのiは点灯してるスイッチの番号と同じ
                if bit & (1 << v):
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False

        if ok: # okなら全ての電球が付いているということ
            res += 1

    print("res : ", res)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import os
from itertools import combinations

def file_input():
    f = open('ABC128/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M=map(int, input().split()) #N:switch M:light
    s=[[] for i in range(M)]
    k=[]
    for i in range(M):
        tmp=list(map(int, input().split()))
        k.append(tmp[0])
        s[i]=tmp[1:]
    p=list(map(int, input().split()))

    out=0
    for i in range(N+1):
        for li in combinations(range(N),i):
            # print(li)
            on=0
            for m in range(M):
                tmp=0
                for j in range(k[m]):
                    # print("m:"+str(m)+" k:"+str(j))
                    for c in li:
                        if s[m][j]==c+1:
                            tmp+=1
                if tmp%2==p[m]:
                    on+=1
            if on==M:
                print(li)
                out+=1

    print(out)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import os
from itertools import combinations

def file_input():
    f = open('ABC128/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M=map(int, input().split()) #N:switch M:light
    s=[[] for i in range(M)]
    k=[]
    for i in range(M):
        tmp=list(map(int, input().split()))
        k.append(tmp[0])
        s[i]=tmp[1:]
    p=list(map(int, input().split()))

    out=0
    for i in range(1,N+1):
        for li in combinations(range(N),i):
            # print(li)
            on=0
            for m in range(M):
                tmp=0
                for j in range(k[m]):
                    # print("m:"+str(m)+" k:"+str(j))
                    for c in li:
                        if s[m][j]==c+1:
                            tmp+=1
                if tmp%2==p[m]:
                    on+=1
            if on==M:
                # print(li)
                out+=1

    print(out)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for bit in product([0, 1], repeat=n):
    onoff = [1] * n # 1がon 0がoff
    ele = True
    for i, j in enumerate(bit):
        if j == 1:
            onoff[i] = 0
    for k in range(m):
        cnt = 0
        for l in range(1,sw[k][0]): #lで横方向
            if onoff[sw[k][l]-1]  == 1:
                cnt += 1
        if cnt % 2 != p[k]:
            ele = False
            break
    if ele :
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for bit in product([0, 1], repeat=n):
    onoff = [1] * n # 1がon 0がoff
    ele = True
    for i, j in enumerate(bit):
        if j == 1:
            onoff[i] = 0
    for k in range(m):
        cnt = 0
        for l in range(1,sw[k][0]): #lで横方向
            if onoff[sw[k][l]-1]  == 1:
                cnt += 1
        if cnt % 2 != p[m-1]:
            ele = False
            break
    if ele :
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

n,m = list(map(int,input().split()))
swi = []
kn = []

for _ in range(m):
    k, *sss = list(map(int,input().split()))
    swi.append(sss)
    kn.append(k)
ppp = list(map(int,input().split()))

ans = 0
sta = list(product((0, 1), repeat=n))

for st in sta:
    cnt = 0
    for l in range(m):
        for o in range(kn[l]):
            if st[swi[l][o] - 1] == 1:
                cnt += 1
        c = cnt % 2
        if c != ppp[l]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# n個のスイッチ
# m個の電球

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

#n,m = 2,2
#a = [[2,1,2],[1,2]]
#p = [0,1]

ans = 0
for i in range(0,2**n): #スイッチの組み合わせを生成
  ck = True
  for j in range(0,m): #j番目の電球が付くかを確認
    # a[j][0]つながっているスイッチの数
    count = 0
    for k in range(0,a[j][0]):
      count += (i >> k) & 1
    if count%2 != p[j]:
      ck = False
      break
  if ck:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#C
n, m = map(int, input().split())
k = [] * m
s = [] * m
p = [] * m
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
# print(k, s, p)
for i in range(2 ** n):
    on = True
    for j in range(m):
        light = 0
        for k in s[j]:
            tmp = i >> k & 1
            light = (light + tmp) % 2
        if light != p[j]:
            on = False
            break
    ans += int(on)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

N, M = map(int, input().split())
sw = []

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

# 剰余がこうなれば正解
p = list(map(int, input().split()))

# スイッチの状態の組み合わせを全列挙
st = list(product([0,1],repeat=N))

ans = [False]*len(st)

for i, s in enumerate(st):
    tmp = []
    for m in range(M):
        on = 0
        for j in range(len(sw[m])):
            on += s[j]
        if (on%2)==p[m]:
            tmp.append(True)
        else:
            tmp.append(False)
    if all(tmp)==True:
        ans[i] = True

print(sum(ans))

Submission status: Wrong Answer

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()))
ans = 0

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

Submission status: Wrong Answer

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

print(switch)
print(poweron)
count = 0
for i in range(m):
  temp = 0
  for j in range(n):
    if i in switch[1:]:
      temp += 1
  if temp == poweron[i]:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
switch=[]
for i in range(2**n):
    kouho=[]
    for j in range(n):
        if (i>>j & 1):
            kouho.append(1)
        else:
            kouho.append(0)
    switch.append(kouho)

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

ans=0
num=0
q=[]
for i in range(len(switch)):
    for j in range(m):
        for k in range(1,len(kyu[j])):
            num=num+switch[i][kyu[j][k]-1]   
        q.append(num%2)
        num=0
    q.reverse()
    if p==q:
      ans=ans+1
    q=[]
    
        
            
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
switch=[]
for i in range(2**n):
    kouho=[]
    for j in range(n):
        if (i>>j & 1):
            kouho.append(1)
        else:
            kouho.append(0)
    switch.append(kouho)

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

ans=0
num=0
q=[]
for i in range(len(switch)):
    for j in range(m):
        num=0
        for k in range(1,len(kyu[j])):
            num=num+switch[i][kyu[j][k]-1]   
        q.append(num%2)
    q.reverse()
    if p==q:
      ans=ans+1
    q=[]
      
        
            
print(ans)

Submission status: Wrong Answer

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

k = []

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

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().strip().split())
k=[]
s=[]
for n in range(M):
    ks=list(map(int,input().strip().split()))
    k.append(ks[0])
    s.append(ks[1:])
p=list(map(int,input().strip().split()))

def judge(k,s,p,l):
    num=0
    ON=True
    for m in range(M):
        for i in range(k[m]):
            if l[s[m][i]-1]==1:
                num+=1
        if num%2!=p[m]:
            ON=False
            break
    return ON             
                
cnt=0
def dfs(l,N,M):
    global cnt
    if len(l)==N:
        if judge(k,s,p,l):
            cnt+=1            
        return
    else:
        for n in range(2):
            l.append(n)
            dfs(l,N,M)
            l.pop()

dfs([],N,M)
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
k=[0]*M
s=[0]*M
for i in range(M):
    ks=list(map(int,input().split()))
    k[i]=ks[0]
    s[i] = [n-1 for n in ks[1:k[i]+1]]
p=list(map(int,input().split()))
ok=0

#スイッチのon/off
def dfs(A):
    global ok
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(A) == N:
        ok+=jg(A)
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

#判定
def jg(A):
    for i in range(M):
        ans=0
        for j in range(k[i]):
            ans+=A[j]
        if ans % 2 != p[i]:
            return 0
    return 1

dfs([])
print(ok)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
k=[0]*M
s=[0]*M
for i in range(M):
    ks=list(map(int,input().split()))
    k[i]=ks[0]
    s[i] = [n-1 for n in ks[1:k[i]+1]]
p=list(map(int,input().split()))
ok=0

#スイッチのon/off
def dfs(A):
    global ok
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(A) == N:
        ok+=jg(A)
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

#判定
def jg(A):
    for i in range(M):
        ans=0
        for j in range(len(s[i])):
            ans+=A[j]
        if ans % 2 != p[i]:
            return 0
    return 1

dfs([])
print(ok)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
k=[0]*M
s=[0]*M
for i in range(M):
    ks=list(map(int,input().split()))
    k[i]=ks[0]
    s[i]=ks[1:k[i]+1]
p=list(map(int,input().split()))
ok=0

#スイッチのon/off
def dfs(A):
    global ok
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(A) == N:
        ok+=jg(A)
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

#判定
def jg(A):
    for i in range(M):
        ans=0
        for j in range(len(s[i])):
            ans+=A[j]
        if ans % 2 != p[i]:
            return 0
    return 1

dfs([])
print(ok)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
count=0
for i in range(2**n):
    flag=False
    judge=[]
    for j in range(m):
        for x in k[j][1:]:
            judge.append(int((i>>x-1)&1))
        finjudge=judge.count(1)
        if finjudge%2==p[j]: continue
        else: 
            flag=True
            break
    if flag: continue
    count+=1        
print(count)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
s = []
for i in range(M):
    tmp = list(map(int, input().split()))
    t = 0
    for j in tmp[1:]:
        t += 1 << (j - 1)
    s.append(t)
p = list(map(int, input().split()))

ans = 0
for i in range(1 << N):
    for x, y in zip(s, p):
        t = i & x
        c = bin(t).count('1') % 2
        if c == y:
            ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
comb = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(2**N)]
result = 0
setting = list()
for i in range(M):
    setting.append(list(map(int,input().split())))
p = list(map(int,input().split()))
for i in comb:
    l = 0
    flag = 0
    for j in setting:
        count = 0
        for k in j:
            if i[k-1] =="1":
                count +=1
        if count % 2 == p[l] :
            flag += 1
        else:
            flag = 0
        l +=1
    if flag ==M:
        result +=1
print(result)

Submission status: Wrong Answer

Solution code:

from itertools import combinations
def main():
    n, m = map(int, input().split())
    cs = []
    for _ in range(m):
        tmpl = list(map(int, input().split()))
        tmpl.pop(0)
        cs.append(set(tmpl))
    p = list(map(int, input().split()))

    r = 0
    switch_patterns = []
    switches = [i for i in range(1, n+1)]
    for i1 in range(1,n+1):
        switch_patterns += combinations(switches, i1)
    switch_patterns_set = []
    for pattern in switch_patterns:
        switch_patterns_set.append(set(pattern))

    for pattern in switch_patterns_set:
        check = []
        for i2 in range(m):
            check.append(len(pattern.intersection(cs[i2])) % 2 == p[i2])
        r += all(check)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
  # N: スイッチの数
  # M: 電球の数
  N,M = list(map(int, input().split()))

  # スイッチの電球の対応表
  # i番目のスイッチに繋がっている電球をビットシフトしながら格納する
  # 0b011 => 3番目繋がっていない、2番目/1番目は繋がっているとおく
  switch_table = [0] * N

  ans = 0

  # 電球とスイッチの対応表を作る
  for i in range(M):
    row = list(map(int, input().split()))
    k = row[0]

    for j in range(1, k+1):
      # 繋がっているスイッチの番号
      # 1-indexed なので、0-indexedにするため1を引く
      s = row[j] - 1

      # 1をiだけビットシフトしたものとORをとると
      # s番目のスイッチに繋がっている電球の情報が入る
      # 0b001 => 1番目と繋がっている
      # 0b100(1 << 2) 3番目と繋がっている
      # 上の 0b001 OR 0b100 => 0b101となり3番目と1番目が繋がっているという寸法
      switch_table[s] |= 1 << i


  # 
  p = 0
  for value in list(map(int, input().split())):
    p |= value << i

  # スイッチを全探索する
  for i in range(1 << N):
    t = 0

    for j in range(N):
      if(i >> j & 1):
        t ^= switch_table[j]

    if(t == p):
      ans += 1

  print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def main():
  # N: スイッチの数
  # M: 電球の数
  N,M = list(map(int, input().split()))

  # スイッチの電球の対応表
  # i番目のスイッチに繋がっている電球をビットシフトしながら格納する
  # 0b011 => 3番目繋がっていない、2番目/1番目は繋がっているとおく
  switch_table = [0] * N

  ans = 0

  # 電球とスイッチの対応表を作る
  for i in range(M):
    row = list(map(int, input().split()))
    k = row[0]

    for j in range(1, k+1):
      # 繋がっているスイッチの番号
      # 1-indexed なので、0-indexedにするため1を引く
      s = row[j] - 1

      # 1をiだけビットシフトしたものとORをとると
      # s番目のスイッチに繋がっている電球の情報が入る
      # 0b001 => 1番目と繋がっている
      # 0b100(1 << 2) 3番目と繋がっている
      # 上の 0b001 OR 0b100 => 0b101となり3番目と1番目が繋がっているという寸法
      switch_table[s] |= 1 << i


  # 
  p = 0
  for value in list(map(int, input().split())):
    p |= value << i

  # スイッチを全探索する
  for i in range(2 ** N):
    t = 0

    for j in range(N):
      if(i >> j & 1):
        t ^= switch_table[j]

    if(t == p):
      ans += 1

  print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
for i in range(1 << N):
    on_cnt = [0] * M
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                if j + 1 in bulbs[k]:
                    on_cnt[k - 1] = (on_cnt[k - 1] + 1) % 2
    if on_cnt == p:
        ans += 1
print(ans)

Submission status: Wrong Answer

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 s in range(1<<N):
    for j in range(M):
        cnt=0
        for h in ks[j][1:]:
            h-=1
            if (s>>h)&1:
                cnt+=1
                cnt%=2
        if cnt!=ks[j][0]:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

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 s in range(1<<M):
    for j in range(M):
        cnt=0
        for h in ks[j][1:]:
            h-=1
            if (s>>h)&1:
                cnt+=1
                cnt%=2
        if cnt!=ks[j][0]:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
sbit = [0] * M
for i in range(M):
  l = list(map(int, input().split()))
  bit = 0
  for j in range(1, l[0]):
    bit += 1 << l[j + 1]
  sbit[i] =  bit
p = list(map(int, input().split()))

total = 0
for tbit in range(2 ** N):
  flg = True
  for i in range(M):
    bit = sbit[i] & tbit
    bits = 0
    while bit > 0:
      if bit & 1:
        bits += 1
      bit = bit >> 1
    if bits % 2 != p[i]:
      flg = False
      break
  if flg:
    total += 1
print(total)

Submission status: Wrong Answer

Solution code:
from itertools import product

N, M = map(int, input().split())
k = [0] * M
s = [[0] for _ in range(M)]
for i in range(M):
    k[i], *s[i] = map(int, input().split())
p = list(map(int, input().split()))
a = list(product([0, 1], repeat=N))  # N=3なら000~111までの8個の直積のリスト
print(a)

ans = 0
for c in a:  # スイッチ状態を全てについて調べる
    cnt = 0
    for i in range(M):  # 電球はM個ある
        tmp = 0
        for t in s[i]:  # s[i]には電球iのスイッチ条件
            tmp += c[t - 1]  # s[i]に書かれていたスイッチのOn／offをtmpに足していく．
            # print("tmp : {}".format(tmp))
        if tmp % 2 == p[i]:
            cnt += 1
    if cnt == M:  # 全ての電球が点灯するなら，組み合わせ数に一つ加える
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    n, m = MI()
    K = []
    S = {}
    for i in range(m):
        l = LI()
        k = l[0]
        s = l[1:]
        # print(k, s)
        K.append(k)
        S[i] = s
    P = LI()

    ans = 0
    # print('aaa', n, m)
    for i in range(pow(2, n)):
        # print(bin(i))
        for v in range(m):
            sv = S[v]
            p = P[v]
            sm = 0
            # print('  sv p', sv, p)

            for j in range(m):
                # print('  i >> j', i >> j, i, j)
                if 1 & (i >> j):
                    if j+1 in sv:
                        sm += 1

            # print('  sm', sm)
            if sm % 2 == p:
                continue
                # pass
            else:
                # print('not p')
                break
        else:
            # print('ans+1')
            ans += 1
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
list_num = list([] for i in range(n))
test = [input().split() for i in range(m)]
check = [0] * n
for i in test:
  list_num[int(i[0]) - 1].append(i[1])
count = 0
count_ac = 0
count_wa = 0
check = 0
for i in list_num:
  for j in range(len(i)):
    if(i[j] =='WA'):
      count += 1
    else:
      count_ac += 1
      check = 1
      break
  if(check == 1):
    count_wa += count
    count = 0
    check = 0 

print(count_ac , count_wa)

Submission status: Wrong Answer

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

ans = 0
for j in range(2**N):
    n = 0  
    for m in range(M):
        t = 0
        for sw in l[m]:
            if (j>>(sw-1)&1):
                print((j>>(sw-1)&1))
                t += 1
        if t%2 == p[m]:
            n += 1
        else:
            break
    if n == M:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

k_list = []
s_list = []
for i in range(M):
    k_s = list(map(int, input().split()))
    k_list.append(k_s[0])
    s_list.append(k_s[1:])

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

ans = 0

for i in range(1 << N):
    all_list = True
    for j in range(M):
        n = 0
        for k in s_list[j]:
            n += bool(i & (1 << k))
        if n % 2 != p_list[j]:
            all_list = False
            break
    ans += all_list

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lis = [None]*M
for i in range(M):
    lis[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
answer = 0

for bit in range(1<<N):
    count =[]
    for i in range(N): #make bit
        mask = 1<<i
        if mask&bit:
            count.append(1)
        else:
            count.append(0)
        #process
    for j in range(M):
        temp = 0
        for k in range(lis[j][0]):
            temp+=count[lis[j][k+1]-1]
        if temp%2 != p[j]:
            break
    else:
        answer+=1
        print(count)
print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import product
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
s = 0
a = 0
for i in product([0,1],repeat=n):
  for j in l:
    for k in j:
  #    print(i,j,k)
      a += i[k-1]
 #   print(a,p[l.index(j)])
    if a%2!=p[l.index(j)]:
      break
    a =0
  else:
    s += 1
print(s)

Submission status: Wrong Answer

Solution code:
from itertools import product
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
s = 0
a = 0
for i in product([0,1],repeat=n):
  for j in l:
    for k in j:
  #    print(i,j,k)
      a += i[k-1]
 #   print(a,p[l.index(j)])
    if a%2!=p[l.index(j)]:
      break
  else:
    s += 1
print(s)

Submission status: Wrong Answer

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

a=[]
for i in range(M):
    for j in range(1,int(List[i][0])+1):
        a.append(int(List[i][j]))
     

count=0
for i in range(1,N+1):
    if 0<=a.count(i)<2:
        count+=1
        
print(2**(count-1) if count!=0 else 0)