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:
import itertools
ans = 0
n,m = map(int, input().split())
s_list = []
s_count_list = []
for _ in range(m):
    s = list(map(int,input().split()))
    s_count_list.append(s[0])
    s_list.append(s[1:])
oe = list(map(int,input().split()))   
seq = list(range(1, n+1))
for i in range(1, n+1):
    cmb = list(itertools.combinations(seq,i))
    for j in range(len(cmb)):
        ansv = []
        for k in range(m):
            ss = []
            for l in range(len(s_list[k])):
                if s_list[k][l] in list(cmb[j]):
                    ss.append(s_list[k][l])
            if len(ss)%2 == oe[k]:
                ansv.append(True)
            else:
                ansv.append(False)
        if all(ansv):
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
mat = np.zeros(N*M).reshape(M, N)

for i in range(M):
    k = list(map(int, input().split()))
    for j in k[1:]:
        mat[i-1, j-1] += 1
p = list(map(int, input().split()))

def two(x):
    a = np.zeros(N)
    for i in range(11):
        if x == 0:
            break
        elif x % 2 == 0:
            x = x // 2
        else:
            a[i] += 1
            x = x // 2
    return a

flag = 0
for i in range(2**N):
    a = two(i)
    mat2 = mat * a
    for j in range(M):
        if np.sum(mat2[j]) % 2 != p[j]:
            break
        if j == M-1:
            flag += 1

print(flag)

Submission status: Wrong Answer

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

# -*- coding: utf-8 -*-


from sys import stdin


############################################

import numpy as np
# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

data = []
for i in range(M):
    write = stdin.readline().split()
    if int(write[0]) == 1:
        data.append(write[1])
    else:
        data.append(write[1:int(write[0])+1])

ans = stdin.readline().split()

count = 0

datas = data

data = [0,1]

M=N

import itertools
if M == 1:
    a = list(itertools.product(data))
elif M == 2:
    a = list(itertools.product(data, data))
elif M == 3:
    a = list(itertools.product(data, data, data))
elif M == 4:
    a = list(itertools.product(data, data, data, data))
elif M == 5:
    a = list(itertools.product(data, data, data, data, data))
elif M == 6:
    a = list(itertools.product(data, data, data, data, data, data))
elif M == 7:
    a = list(itertools.product(data, data, data, data, data, data, data))
elif M == 8:
    a = list(itertools.product(data, data, data, data, data, data, data, data))
elif M == 9:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data))
elif M == 10:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data))


for element in a:
    for i, d in enumerate(datas):
        x = 0
        sum = 0
        if len(d) != 1:
            for dd in d:
               sum += element[int(dd)-1] 
        else:
           sum += element[int(d)-1]
        if sum%2 == int(ans[i]):
           continue
        else:
           x = 1
           break
    if x == 0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input=sys.stdin.readline

N,M = map(int,input().split())
ks=[0]*M
for i in range(M):
  ks[i] = list(map(int,input().split()))
ps = list(map(int,input().split()))

X = 2**N
pf = -1
for p in ps:
  if X >= 2:
    X//=2
  else:
    if pf != p:
      print(0)
      exit()
  pf = p
print(X)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = 0
l=[]
for i in range(M):
  l.append(input().split())
p = [int(x) for x in input().split()]
for i in range(2 ** N):
  on = 0
  sw = [int(x) for x in list(bin(i)[2:].zfill(N))]
  for j in range(M):
    s = 0
    for k in range(1,int(l[j][0])+1):
      s += int(sw[N - k])
    if s % 2 == p[j]:
      on += 1
  if on == M:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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

result = 0
for m in range(2**N):
    switches = list(map(int, list(str(bin(m))[2:])))
    switches = [0]*(N-len(switches)) + switches

    flag = True
    for idx, bulb in enumerate(bulbs):
        count = 0
        for switch in range(len(bulb)):
            count += switches[switch-1]
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Wrong Answer

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

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

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

result = 0
for m in range(2**N):
    switches = list(map(int, list(str(bin(m))[2:])))
    switches = [0]*(N-len(switches)) + switches

    flag = True
    for idx, bulb in enumerate(bulbs):
        count = 0
        for switch in range(len(bulb)):
            count += switches[switch]
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
N,M=[int(i) for i in input().split()]
list=[];list1=[];list3=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
for i in range(M):
  list+=[int(i) for i in input().split()]
  list1+=[list]
  list=[]
#  print(list1)
list2 = [int(i) for i in input().split()]
#print(list2)
for i in range(M):
  for j in range(list1[i][0]):
    n=list1[i][j+1]
#    print(i,j,n)
    if list3[n]==-1:list3[n]=list2[i]
    if list3[n]==-2:continue
    if list3[n]!=list2[i]:list3[n]=-2
#print(list1,list2,list3)
print(2**(list3.count(0)+list3.count(1)))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
mat = np.zeros(N*M).reshape(M, N)

for i in range(M):
    k = list(map(int, input().split()))
    for j in k[1:]:
        mat[i-1, j-1] += 1
p = list(map(int, input().split()))

def two(x):
    a = np.zeros(N)
    for i in range(10):
        if x == 0:
            break
        elif x % 2 == 0:
            x = x // 2
        else:
            a[i] += 1
            x = x // 2
    return a

flag = 0
for i in range(2**N):
    a = two(i)
    mat2 = mat * a
    for j in range(M):
        if np.sum(mat2[j]) % 2 != p[j]:
            break
        if j == M-1:
            flag += 1

print(flag)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
a=[]
for i in range(k):
    p=list(map(int,input().split()))
    p=p[1:]
    a.append(p)
r=list(map(int,input().split()))
ans=0
cou=0
for i in range(k):
    for j in range(k):
        if a[i]==a[j]:
            if r[i]!=r[j]:
                ans=1
            else:
                cou+=1
cou-=k
cou/=2
k-=cou
if n<k:
    print(0)
else:
    print(int(2**(n-k)))

Submission status: Wrong Answer

Solution code:
def is_all_lighting(switch_patten, s_info_list, p_list):
    for i in range(len(s_info_list)):
        s_info = s_info_list[i]
        on_count = 0
        for s in s_info['s_list']:
            on_count += switch_patten // (2 ** (s - 1)) % 2
        if on_count % 2 != p_list[i]:
            return False
    return True


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

for _ in range(M):
    val_list = list(map(int, input().split()))
    s_info_list.append({
        'k': val_list[0],
        's_list': val_list[1:]
    })
p_list = list(map(int, input().split()))

count = 0

for pattern in range(1, 2 ** N):
    if is_all_lighting(pattern, s_info_list, p_list):
        count += 1

print(count)

Submission status: Wrong Answer

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

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

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

result = 0
for m in range((2**N)-1):
    switches = list(map(int, list(str(bin(m))[2:])))
    switches = [0]*(N-len(switches)) + switches

    count = 0
    flag = True
    for idx, bulb in enumerate(bulbs):
        for switch in range(len(bulb)):
            count += switches[switch]
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Wrong Answer

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

# -*- coding: utf-8 -*-


from sys import stdin



############################################

import numpy as np
# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

data = []
for i in range(M):
    write = stdin.readline().split()
    if int(write[0]) == 1:
        data.append(write[1])
    else:
        data.append(write[1:int(write[0])+1])

ans = stdin.readline().split()

count = 0

datas = data

data = [0,1]

M=N

import itertools
if M == 1:
    a = list(itertools.product(data))
elif M == 2:
    a = list(itertools.product(data, data))
elif M == 3:
    a = list(itertools.product(data, data, data))
elif M == 4:
    a = list(itertools.product(data, data, data, data))
elif M == 5:
    a = list(itertools.product(data, data, data, data, data))
elif M == 6:
    a = list(itertools.product(data, data, data, data, data, data))
elif M == 7:
    a = list(itertools.product(data, data, data, data, data, data, data))
elif M == 8:
    a = list(itertools.product(data, data, data, data, data, data, data, data))
elif M == 9:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data))
elif M == 10:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data))


for element in a:
    for i, d in enumerate(datas):
        x = 0
        sum = 0
        try:
            for dd in d:
               sum += element[int(dd)-1] 
        except:
           sum += element[int(d)-1]
        if sum%2 == int(ans[i]):
           continue
        else:
           x = 1
           break
    if x ==0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
switch=[ '0' * (10) for i in range(m)]
for i in range(m):
    li = list(map(int,input().split()))
    for j in range(len(li)):
        if j==0:
            continue
        lis = list(switch[i])
        lis[li[j]-1] = '1'
        switch[i] = ''.join(lis)
p=list(map(int,input().split()))
ans=0
# print(switch)
for i in range(2**n):
    on_switch=list(format(i,'010b')[::-1])
    flag=1
    for ii in range(m):
        s=switch[ii]
        icchi=0
        for z in range(10):
            if on_switch[z]=='1':
                if list(s)[z] == '1':
                    icchi+=1
        # print(''.join(on_switch),switch[ii])
        # print(i,ii,icchi)
        if icchi%2 != p[ii-1]:
            flag=0
            break
    if flag==1:
        ans+=1
        # print('yeah',i)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
a=[]
for i in range(k):
    p=list(map(int,input().split()))
    p=p[1:]
    a.append(p)
r=list(map(int,input().split()))
ans=0
cou=0
for i in range(k):
    for j in range(k):
        if a[i]==a[j]:
            if r[i]!=r[j]:
                ans=1
            else:
                cou+=1
cou-=k
cou/=2
k-=cou
if n<k:
    print(0)
else:
    print(2**(n-k))

Submission status: Wrong Answer

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

def decli(n):
    return n - 1
for i in range(m):
    s = list(map(int, input().split()))
    s = s[1:]
    s = list(map(decli, s))
    lig.append(s)
p = list(map(int, input().split()))

cnt = 0
for i in range(2 ** n):
    switch = []
    tmp = i
    for j in range(n):
        switch.append(tmp % 2)
        tmp //= 2
    all_flg = 1
    for lig_no in range(m):
        flg = 0
        for j in range(len(lig[lig_no])):
            flg ^= switch[j]
        if flg != p[lig_no]:
            all_flg = 0
            break
    if all_flg == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

z = list(itertools.combinations_with_replacement([1,0],n))
ans = 0
for i in z:
    ad = True
    for j in range(m):
        cnt = 0
        for l in range(k[j]):
            if i[s[j][l]-1] == 1:
                cnt += 1
        if not cnt%2 == p[j]:
            ad = False
            break
    if ad:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
K = [0]*M
S = [[0] *N for _ in range(M)]
for i in range(M):
    tmp = list(map(int,input().split()))
    K[i] = tmp[0]
    for s in tmp[1:]:
        S[i][s-1] = 1
P = list(map(int,input().split()))

ptns = list(itertools.product((0,1),repeat=N))
ans = 0
for p in ptns:
    ok = True
    on_count = 0
    for i in range(M):
        for j in range(N):
            on_count += S[i][j] and p[j]
        if on_count%2 != P[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce
def c():
    p = [[int(t) for t in r.split(' ')] for r in sys.stdin.read().split('\n') if r != '']
    N, M = p[0]
    l = p[1:M + 1]
    cond = p[M + 1]
    count = 0
    for i in range(0, 1<<N):
        cc = 0
        for j in range(0, M):
            b = 0b0
            for k in l[j]:
                if (i >> (k - 1)) & 0b1 == 1:
                    b = ~b
            if b & 0b1 != cond[j]:
                break
            cc = cc + 1
        if cc == M:
            count = count + 1
    print(count)
c()

Submission status: Wrong Answer

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

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

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

result = 0
for m in range(2**N):
    switches = list(map(int, list(str(bin(m))[2:])))
    switches = [0]*(N-len(switches)) + switches

    count = 0
    flag = True
    for idx, bulb in enumerate(bulbs):
        for switch in range(len(bulb)):
            count += switches[switch]
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Wrong Answer

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

# -*- coding: utf-8 -*-


from sys import stdin


############################################

import numpy as np
# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

data = []
for i in range(M):
    write = stdin.readline().split()
    if int(write[0]) == 1:
        data.append(write[1])
    else:
        data.append(write[1:int(write[0])+1])

ans = stdin.readline().split()

count = 0

datas = data

import numpy as np
data = [0,1]

M=N

import itertools
if M == 1:
    a = list(itertools.product(data))
elif M == 2:
    a = list(itertools.product(data, data))
elif M == 3:
    a = list(itertools.product(data, data, data))
elif M == 4:
    a = list(itertools.product(data, data, data, data))
elif M == 5:
    a = list(itertools.product(data, data, data, data, data))
elif M == 6:
    a = list(itertools.product(data, data, data, data, data, data))
elif M == 7:
    a = list(itertools.product(data, data, data, data, data, data, data))
elif M == 8:
    a = list(itertools.product(data, data, data, data, data, data, data, data))
elif M == 9:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data))
elif M == 10:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data))


for element in a:
    for i, d in enumerate(datas):
        x = 0
        sum = 0
        try:
            for dd in d:
               sum += element[int(dd)-1] 
        except:
           sum += element[int(d)]
        if sum%2 == int(ans[i]):
           continue
        else:
           x = 1
           break
    if x ==0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

MOD = 2  # type: int


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N,M = map(int,input().split())
    from collections import defaultdict
    d = defaultdict()
    for i in range(M):
        l = list(map(int,input().split()))
        d[i] = l[1:]

    # for k,v in d.items():
    #     print(k,v)

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

    ans = 0
    import itertools
    s = ('on', 'off')
    for i in itertools.product(s, repeat=N):
        anst = 0
        for k,v in d.items():
            if(len([x for x in v if(i[x-1] == 'on')])%2 == p[k-1]):
                anst += 1

        if(anst == M):
            ans += 1
    
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# -*- coding: utf-8 -*-


from sys import stdin



############################################

import numpy as np
# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

data = []
for i in range(M):
    write = stdin.readline().split()
    if int(write[0]) == 1:
        data.append(write[1])
    else:
        data.append(write[1:int(write[0])+1])

ans = stdin.readline().split()

count = 0

datas = data

import numpy as np
data = [0,1]

M=N

import itertools
if M == 1:
    a = list(itertools.product(data))
elif M == 2:
    a = list(itertools.product(data, data))
elif M == 3:
    a = list(itertools.product(data, data, data))
elif M == 4:
    a = list(itertools.product(data, data, data, data))
elif M == 5:
    a = list(itertools.product(data, data, data, data, data))
elif M == 6:
    a = list(itertools.product(data, data, data, data, data, data))
elif M == 7:
    a = list(itertools.product(data, data, data, data, data, data, data))
elif M == 8:
    a = list(itertools.product(data, data, data, data, data, data, data, data))
elif M == 9:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data))
elif M == 10:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data))


for element in a:
    for i, d in enumerate(datas):
        x = 0
        sum = 0
#        try:
        for dd in d:
           sum += element[int(dd)-1] 
#        except:
#           sum += element[int(d)]
        if sum%2 == int(ans[i]):
           continue
        else:
           x = 1
           break
    if x ==0:
        count+=1
#    for i in range(int(write[0])):
#    write
print(count)

Submission status: Wrong Answer

Solution code:
# まずはナイーブに書く
# スイッチは0から始まる

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

light_s_dict = dict()
# 繋がっているスイッチ
for i in range(M):
    l = [int(j) for j in input().split()]
    connected_s = [0]*N
    for s in l[1:]:
        connected_s[s-1] = 1
    light_s_dict[i] = connected_s

# スイッチの全パターン
s_patterns = []
for i in range(2**N):
    p_str = bin(i)[2:].zfill(N)
    s_patterns.append([int(i) for i in list(p_str)])
    
# 点灯条件
light_conditions = [int(p) for p in input().split()]

# 全探索
ans = 0
for pattern in s_patterns:
    for light in range(M): # 全部のlightに対して
        cond = 0 # onをカウント
        for i, p in enumerate(pattern): # 各パターンの個々のスイッチに対して
            if p == 1:
                cond += light_s_dict[light][i] # 繋がっているスイッチ
        if cond % 2 != light_conditions[light-1]:
            break
    else: # 全てのlightに対して正常に終了すれば
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [[int(elem)-1 for elem in fin().split()] for _ in range(M)]
p_list = [int(elem) for elem in fin().split()]

count = 0
perm_list = list(range(0, N))
for r in range(1, len(perm_list)+1):
    for each_iter in itertools.combinations(perm_list, r):
        each_switchs = np.zeros((N))
        each_iter = list(each_iter)
        each_switchs[each_iter] = 1
        flag = 0
        for i, each_condition in enumerate(conditions):
            each_sum = each_switchs[each_condition[1:]]
            if np.sum(each_sum) % 2 != p_list[i]:
                flag = 1
        if flag == 0:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools
target = (0, 1)
N,M = map(int,input().split())
sk_ = [list(map(int,input().split())) for _ in range(M)]
P_ = list(map(int,input().split()))
max_n = 0
state = list(itertools.product(target,repeat=N))
#print(state)
for i in state:
  #print('state : {}'.format(i))
  num = 0
  ons = 0
  for j in range(M):
    #print('m : {}'.format(j))
    for s in sk_[j][1:]:
      #print('s : {}'.format(s))
      if i[s-1] == 1:
        num += 1
    if num%2 == P_[j]:
      ons += 1
  #print('ons : {}'.format(ons))
  if ons == M:
    max_n += 1
    
print(max_n)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    B = []
    for _ in range(M):
        A = [0] * (N + 1)
        ks = list(map(int, input().split()))
        for s in ks[1:]:
            A[s] = 1
        B.append(A)
    P = list(map(int, input().split()))
    ans = int('1' * N, 2)
    for A, p in zip(B, P):
        A[0] = p
        ans &= int(''.join(map(str, A)), 2)
    print(ans)


main()

Submission status: Wrong Answer

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

swi = [[0] * N for _ in range(2**N)]
for i in range(2**N):
    for j in range(N):
        if (i // 2**j) % 2 == 1:
            swi[i][j] = 1

ans = 0
for b in range(2**N):
    done = True
    for i in range(M):
        now = 0
        for k in range(K[i]):
            now += swi[b][k]
        if now % 2 != P[i]:
            done = False
            break
    if done:
        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()))

switch = []
for i in range(N**2):
    tmp = []
    for j in range(N):
        if (i >> j) & 1:
            tmp.append(j+1)
    switch.append(tmp)
switch.append([i for i in range(1,N+1)])

cnt = 0
for s in switch:
    judge = True
    for idx,ks in enumerate(KS):
        kcnt = 0
        for k in ks[1:]:
            kcnt += s.count(k)
        if kcnt % 2 == P[idx]:
            continue
        judge = False
        break
    if judge:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().rstrip().split())
k_s = [list(map(int, input().rstrip().split())) for _ in range(M)]
for i in range(M):
    k_s[i].pop(0)
P = list(map(int, input().split()))
#on=1,off=0
count = 0
counter = 0
limit = 2**N
for i in range(2):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for m in range(2):
                    for n in range(2):
                        for o in range(2):
                            for p in range(2):
                                for q in range(2):
                                    for r in range(2):
                                        counter += 1
                                        stats = [r,q,p,o,n,m,l,k,j,i]
                                        index = 0
                                        flg = True
                                        for s in k_s:
                                            sums = 0
                                            for t in s:
                                                sums += stats[t-1]
                                            rem = sums % 2
                                            if rem == P[index]:
                                                flg = False
                                                break
                                            index += 1
                                        if flg:
                                            count += 1
                                        if limit == counter:
                                            print(count)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
for i in range(k):
    input()
if n<k:
    print(0)
else:
    print(2**(n-k))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
taiou = np.zeros((N,M))
for i in range(M):
    val =  input().split()
    for j in range(int(val[0])):
        v = int(val[j+1])
        taiou[v-1][i] = 1
p = np.array([int(v) for v in input().split()])
cnt = 0
for val in range(2**N):
    v = taiou*np.array([[int(i)] for i in bin(val)[2:].zfill(N)])
    if np.sum(np.sum(v,axis=0)%2==p)==0:
        cnt+=1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
# まずはナイーブに書く
# スイッチは0から始まる

N, M = map(int, input().split())
light_s_dict = dict()
light_n_dict = dict()

# 繋がっているスイッチ
for i in range(1, M+1):
    l = [int(j) for j in input().split()]
    connected_s = [0]*N
    for s in l[1:]:
        connected_s[s-1] = 1
    light_s_dict[i] = connected_s
    light_n_dict[i] = l[0]

# スイッチの全パターン
s_patterns = []
for i in range(2**N):
    p_str = bin(i)[2:].zfill(N)
    s_patterns.append([int(i) for i in list(p_str)])
    
# 点灯条件
light_conditions = [int(p) for p in input().split()]

# 全探索
ans = 0
for pattern in s_patterns:
    cond = 0
    for light in range(1, M+1): # 全部のlightに対して
        for i, p in enumerate(pattern):
            if p == 1:
                cond += light_s_dict[light][i]
        if cond % 2 != light_conditions[light-1]:
            break
    else: # 全てのlightに対して正常に終了すれば
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ks = []
ss = []
for i in range(m):
    row = list(map(int, input().split()))
    k = row.pop(0)
    ss.append(row)


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

ks = np.array(ks, dtype=np.int64)
ps = np.array(ps, dtype=np.int64)

masks = []
for s in ss:
    mask = sum([2 ** (a - 1)for a in s])
    masks.append(mask)


# 電球iにつながっていて、ONになっているスイッチの個数を2で割ったあまり
def calc_switch_state(i, switch_state):
    num_on = 0
    mask = masks[i]
    switch_state = switch_state & mask
    while switch_state > 0:
        num_on += switch_state % 2
        switch_state //= 2

    return num_on % 2

# i 番目の電球がスイッチの状態sで点灯するかどうか
def is_light_on(i, switch_state):
    return calc_switch_state(i, switch_state) == ps[i]

# 探索
total = 0
for state in range(2**n):
    if all([calc_switch_state(i, state) for i in range(m)]):
        total += 1

print(total)

Submission status: Wrong Answer

Solution code:
#ABC128C-Switches.py

from sys import stdin
import itertools

input = stdin.readline

N, M = list(map(int, input().split()))
switches = [[0 for _ in range(M)] for _ in range(N)]
allSwitches = [i for i in range(N)]
totalNumber = 0

for i in range(M):
    ks = list(map(int, input().split()))
    for j in range(1,len(ks)):
        switches[ks[j]-1][i] = 1

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

def check(list):
    if P == [a%2 for a in list]:
        return 1
    else:
        return 0

for i in range(N+1):
    cList = list(itertools.combinations(allSwitches,i))
    for clist in cList:
        sumList = [0 for _ in range(N)]
        for c in clist:
            sumList = [x+y for (x,y) in zip(sumList,switches[c])]
        totalNumber += check(sumList)
    if cList == []:
        asumList = [0 for _ in range(N)]
        totalNumber += check(asumList)


print(totalNumber)

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
ks=list(list(map(int,input().split())) for _ in range(M))
P=list(map(int,input().split()))
L=[0,1]
LL=list(itertools.product(L,repeat=N))
ans=0
sum=[]
msum=0
for I in LL:
    sum=[]
    for J in ks:
        msum=0
        for k in range(1,J[0]+1):
            msum+=I[J[k]-1]
            sum.append(msum)
    if all(sum[i]%2==P[i] for i in range(M)):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
bi_N = [i for i in range(2**N-1)]
ans = 0
for i in bi_N[::-1]:
  print(i)