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().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]
                                        stats = stats[:N]
                                        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
                                        if flg:
                                            count += 1
                                        if limit == counter:
                                            print(count)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))


def convert(nums):
    return sum([2^(i-1) for i in nums])


def is_on(ons, bulb, p):
    return bin(ons & bulb).count('1') % 2 == p

def is_all_on(ons, bulbs, ps):
    res = True
    for bulb, p in zip(bulbs, ps):
        res &= is_on(ons, bulb, p)
    return res


n, m = LI()
k, s = [], []
for _ in range(m):
    _input = LI()
    k.append(_input[0])
    s.append(convert(_input[1:]))

p = LI()

res = 0
for ons in range(2**n):
    # print(ons, j, is_on(ons, s[j], p[j]))
    res += is_all_on(ons, s, p)

print(res)

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):
                                        if limit == counter:
                                            print(count)
                                        counter += 1
                                        stats = [r,q,p,o,n,m,l,k,j,i]
                                        stats = stats[:N]
                                        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
                                        if flg:
                                            count += 1

Submission status: Wrong Answer

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

l = max(ks[0])
for m in range(1,M):
    l = max(l,max(ks[m]))

lis_swi = [[] for i in range(l)]

for m in range(M):
    for s in ks[m][1:]:
        lis_swi[s-1].append(m)


ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in lis_swi[j]:
                cnt_on[m] +=1

    f = True
    for m in range(M):
        if cnt_on[m]%2 != p[m]:
            f = False
            break
    
    if f:
        ans += 1


print(ans)

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)

print(totalNumber)

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)

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

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ks = []
switch_list = [[] for i in range(M)]
for i in range(M):
    ks.append(list(map(int, input().split())))
    for j in range(10-ks[i][0]):
        switch_list[i].append(0)
    for j in range(ks[i][0]):
        switch_list[i].insert(10-ks[i][j+1],1)
p = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    flg = True
    binary = format(i, 'b').zfill(10)
    binary = list(map(int, binary))
    for j in range(M):
        on = np.logical_and(switch_list[j], binary)
        total_on = sum(on)
        if total_on%2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
ks = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
switch = [i for i in range(n)]
c = 0
for i in range(2**n):
  li = []
  flag = False
  for j in range(m):
    if ((i>>j)&1):
      li.append(j+1)
  for j in range(m):
    s = set(li)
    ss = set(ks[j])
    s = s & ss
    if len(s) % 2 == p[j]:
      flag = True
    else:
      flag = False
      break
  if flag:
    c += 1
print(c)

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):
    cList = list(itertools.combinations(allSwitches,i+1))
    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)

print(totalNumber)

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()))
# print(N, M)
# print(ks)
# print(p)

ans = 0

import itertools
for i in itertools.product([0,1], repeat=N):
  righted = 0
  for iter, j in enumerate(ks):
    cnt = 0
    for k in range(1,len(j)):
      cnt += i[k-1]
    if cnt % 2 == p[iter]:
      righted += 1
  if len(ks) == righted:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def add1(s, i = -1):
    if s[i] == 0:
        s[i] = 1
        return s
    else:
        s[i] = 0
        return add1(s, i-1)
    
n, m = map(int, input().split())

k = []
s = []

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

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

sw = np.zeros(n)

ons = 0
ans = 0
sums = 0

for i in range(0, 2**n):
    for j in range(0, m):
        for l in s[j]:
            ons += sw[l-1]
        if ons % 2 == p[j]:
            sums += 1
    if sums == m:
        ans += 1
    sums = 0
    ons = 0
    if i != 2**n - 1:
        sw = add1(sw)


print(ans)

Submission status: Wrong Answer

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

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

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

res = 0
for i in range(2**n):
    cou = [0 for k in range(m)]
    binary = bin(i)[2:]
    for j in range(len(binary)):
        if binary[j] == '1':
            for k in range(len(lis)):
                if j + 1 in lis[k]:
                    cou[k] += 1 
    if all((cou[x] - plist[x])%2 == 0 for x in range(m)):
        res += 1
print(res)

Submission status: Wrong Answer

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

ss = []
for i in range(m):
    s = list(map(int, input().split()))[1:]
    te = 0
    for sm in s:
        te += 2**(sm-1)
    ss.append(te)

pp = list(map(int, input().split()))
res = 0
for i in range(2**(n-1)):
    tm = True
    for j in range(len(ss)):
        if (i & ss[j]) % 2 != pp[j]:
            tm = False
            break
    if tm:
        res += 1
print(res)

Submission status: Wrong Answer

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

for i in range(2 ** N):
    hoge = bin(i + 1)
    hoge = str(hoge)
    hoge = hoge[2:]
    hoge = hoge.zfill(len(str(bin((2 ** N)))) - 2)
    result = True
    for j in range(M):
        onon = 0
        for k in s[j][1:]:
            if hoge[k] == "1":
                onon += 1
        if onon % 2 != p[j]:
            result = False
    if result:
        print("OK")
        print(hoge)
        result2 += 1
print(result2)

Submission status: Wrong Answer

Solution code:
import itertools

n, m = [int(_) for _ in input().split()]
ks = []
cnt = 0

for i in range(m):
    ks.append([int(_) for _ in input().split()])
p = [int(_) for _ in input().split()]

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

Submission status: Wrong Answer

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

ans = 0
for i in range(1, 2**N):
    num = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            SS[j] = 1
    flg = True
    for j, s in enumerate(S):
        num = 0
        for e in s:
            if SS[e-1] == 1:
                num += 1
        if num % 2 != P[j]:
            flg = False
            break
    if flg:
        ans += 1
    SS = [0] * N   
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
s = []
for i in range(m):
  s.append([i - 1 for i in list(map(int, input().split()))[1:]])
p = list(map(int, input().split()))
r = 0
for i in range(2 ** n):
  lst = list(map(int, bin(i)[2:].zfill(n)))
  f = True
  for j in range(m):
    if len(s[j]) > 2:
      getter = itemgetter(*s[j])
      if sum(getter(lst)) % 2 != p[j]:
        f = False
        break
    else:
      if lst[s[j][0]] % 2 != p[j]:
        f = False
        break
  if f:
    r += 1
print(r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        kk, *rest = map(int, input().split())
        K.append(kk)
        S.append(rest)
    P = list(map(int, input().split()))
    # print(N, M)
    # print(K, S, P)

    base = [1]
    for i in range(10):
        base.append(base[-1]*2)
    base = reversed(base)

    counter = 0
    for n in range(1, 2**N):    # 全探索
        flag = True
        # print("{0:04b}".format(n))
        for k, s, p in zip(K, S, P):
            # print(k, s, p)
            sumof = 0
            for ss in s:
                sumof += (n >> (ss-1)) % 2
            sumof %= 2
            if sumof != p:
                flag = False
                break
        if flag:
            counter += 1
    print(counter)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(m):
    l = list(map(int,input().split()))
    K.append(l[1:])
res = 0
p = list(map(int,input().split()))
for i in range(2**n):
    s=format(i,'#0'+str(n)+'b')
    s=s[2:]
    cnt = [0]*m
    for j in range(len(s)):
        if s[j] == '0':
            continue
        for k in range(len(K)):
            if (j+1) in K[k]:
                cnt[k]+=1
    flag = True

    for j in range(len(cnt)):
        if cnt[j]%2 != p[j]:
            flag = False
            break
    if flag:
        res += 1 
print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:00 2019

@author: Yamazaki Kenichi
"""

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

ans = 0
for i in range(2**N):
    t = '{:010b}'.format(i)
    flg = True
    for j in range(M):
        tmp = 0
        for k in range(ks[j][0]):
            tmp += int(t[-ks[j][k]])
#        print(i,j,t,tmp,ans)
        if tmp%2 == p[j]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1

            
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
s_info = [[False for i in range(M)] for j in range(N)]
for i in range(M):
	l = list(map(int,input().split()))
	for j in range(1, l[0]+1):
		s_info[j-1][i] = True
cond = list(map(int,input().split()))


def dec2bin(n, d):
	ret = []
	for i in range(d):
		ret.append(n%2)
		n = n // 2
	return ret

ans = 0
for i in range(2**N):
	switch = dec2bin(i, N)
	flg = True
	for m in range(M):
		if sum([1 for n in range(N) if switch[n] == 1 and s_info[n][m]]) % 2 != cond[m]:
			flg =False
			break
	if flg:
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = []
for i in range(m):
  l = list(map(int,input().split()))
  l.remove(l[0])
  lis.append(l)
ch = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
  key = 1
  s = str(format(i,"b").zfill(n))
  num = 0
  for j in range(m):
    for nu in lis[j]:
      if s[nu-1] == "1":
        num += 1
    if num % 2 != ch[j]:
      key = 0
  if key == 1:
    ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**N):
  switch = []
  for j in range(N):
    switch.append((i >> j) & 1)
  lights = 0
  connect = 0
  for u in range(M):
    for v in range(KS[u][0]):
      if switch[KS[u][v+1]-1] == True:
        connect += 1
    if connect % 2 == P[u]:
      lights += 1
  if lights == M:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1::] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    f = True
    bag = []
    total = 0
    for j in range(0, N):  # このループが一番のポイント
        if (i >> j) & 1:  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(j + 1)
    for s in S:
        for ss in s:
            if ss in bag:
                total += 1
        if total % 2 != P[S.index(s)]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(x) for x in input().split()]


inn = []
for i in range(M):
    inn.append([int(x) for x in input().split()][1:])
    
p = [int(x) for x in input().split()]
ans = 0
for i in range(2**N):
    b = "0"*(N-len(bin(i)[2::]))+bin(i)[2::]
 #   print(b)
    s = 0
    flag = True
    for j in range(M):
        for k in inn[j]:
            if b[k-1] == "1":
                s += 1
    
        if s % 2 != p[j]:
            flag = False
#            print(b,s)
            break
        
    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product
n,m=map(int, input().split())

a=[list(map(int, input().split())) for i in range(m)]
p=list(map(int, input().split()))
count=0
for sw in product([0,1],repeat=n):
    flag=1
    on=0
    for i in range(m):
        for j in range(a[i][0]):
            on+=sw[a[i][j+1]-1]
        
        if on%2!=p[i]:
            flag=0
        #print(on,sw,p[i],flag, on%2!=p[i])
    count+=flag
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
    _, *s, = map(int, input().split())
    for v in s:
        S[i] = S[i] | (2 << v)

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

ans = 0
for p in range(2**(N + 1)):
    ok = True
    for i in range(M):
        b = format(p & S[i], 'b')
        if b.count('1') % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product


def li():
    return list(map(int, input().split()))


def is_on(state, p, s_list):
    return sum(list(map(lambda x: state[x - 1], s_list))) % 2 == p


if __name__ == '__main__':
    [n, m] = li()
    ks_list = [li() for _ in range(m)]
    p_list = li()

    pattern = 0

    for state in product([0, 1], repeat=n):
        is_all = True
        for index, ks in enumerate(ks_list):
            if not is_on(state, p_list[index], ks[:1]):
                is_all = False
        if is_all:
            pattern = pattern + 1
    print(pattern)

Submission status: Wrong Answer

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

for i in range(m):
    l = list(map(int,input().split()))
    K.append(l[1:])
res = 0
p = list(map(int,input().split()))
for i in range(2**n):
    s=format(i,'#0'+str(n)+'b')
    s=s[2:]
    cnt = [0]*m
    for j in range(len(s)):
        for k in range(len(K)):
            if s[j]=='1' and (j+1) in K[k]:
                cnt[k]+=1
    flag = True

    for j in range(len(cnt)):
        if cnt[j]%2 != p[j]:
            flag = False
            break
    if flag:
        res += 1 
print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
    _, *s, = map(int, input().split())
    for v in s:
        S[i] = S[i] | (2 << v)

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

ans = 0
for p in range(2**N + 1):
    ok = True
    for i in range(M):
        b = format(p & S[i], 'b')
        if b.count('1') % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it

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

s = []

for i in range(m):

    k, *temp = map(int, input().split())

    s.append(set(temp))

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

ans = 0

for i in range(1, n + 1):

    for comb in it.combinations(list(range(1, n + 1)), i):

        flag = [False] * m

        for j in range(m):

            if sum([c in s[j] for c in comb]) % 2 == p[j]:
                flag[j] = True

        if all(flag):
            ans += 1

print(ans)

Submission status: Wrong Answer

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

flgs = [0]*M
for i in range(M):
	k,*vals = map(int,input().split())
	for v in vals:
		flgs[i] |= 1 << (v-1)

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

cnt = 0
for bit in range(2**N):
	cnt_tmp = 1
	for f in flgs:
		if len([j for j in range(N) if ((f&bit) & (1<< j)) != 0]) % 2 != p[i]:
			cnt_tmp = 0
	cnt += cnt_tmp
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
    _, *s, = map(int, input().split())
    for v in s:
        S[i] = S[i] | (2 << v)

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

ans = 0
for p in range(2**N):
    ok = True
    for i in range(M):
        b = format(p & S[i], 'b')
        if b.count('1') % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
s_info = [[False for i in range(M)] for j in range(N)]
for i in range(M):
	l = list(map(int,input().split()))
	for j in range(1, l[0]+1):
		s_info[j-1][i] = True
cond = list(map(int,input().split()))


def func(switch, n):
	if n != N:
		n_switch = [i for i in switch]
		for i in range(M):
			if s_info[n][i]:
				n_switch[i] += 1
		return func(switch, n+1) + func(n_switch, n+1)
	else:
		for i in range(M):
			if switch[i]%2 == cond[i]:
				continue
			else:
				return 0
		return 1

switch = [0 for i in range(M)]
print(func(switch, 0))

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

c = 0
for i in range(2**n):
    t = format(i,"010b")
    s = t[10-n:]
    q = 0
    r = 0
    for j in range(m):
        for u in range(k[j][0]):
            q += int(s[k[j][u+1]-1])
        if q % 2 == p[j]:
            continue
        else:
            r = 1
            break
    if r == 0:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
li = [[] for _ in range(N)]
for i in range(M):
    for ma in s[i]:
        li[ma - 1].append(i)
ans = 0
print(li)
for i in range(2 ** N):
    l = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for r in li[j]:
                l[r] ^= 1
    if l == p:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    N, M = map(int, input().split())

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

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

    # print(S)
    # print(P)

    ans = 0
    # Bit 全探索
    pattern = 1 << N
    for i in range(pattern):
        scope = []
        for j in range(N):
            if (i >> j) & 1:
                scope.append(j + 1)

        if len(scope) == 0:
            continue
        # print('pattern = {}'.format(scope))

        turn_on = True
        for j in range(len(S)):
            switches = S[j]
            c = 0
            for states in scope:
                if states in switches:
                    c += 1
            if c % 2 != P[j]:
                turn_on = False
            if not turn_on:
                break
        if turn_on:
            # print('ok = {}'.format(scope))
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections


N,M = map(int, sys.stdin.readline().rstrip().split(" "))
switches = []
for _ in range(M):
    k, *s = map(int, sys.stdin.readline().rstrip().split(" "))
    # switches.append(s)
    switch_bit = sum(2**v for v in s)
    switches.append(switch_bit)
ps = list(map(int, sys.stdin.readline().rstrip().split(" ")))



result = 0
for i in range(2**N):
    for j,switch in enumerate(switches):
        pattern = switch | i
        if not bin(pattern).count("1") % 2 == ps[j]:
            break
    else:
        result += 1
print(result)


exit(0)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
li = [[] for _ in range(N)]
for i in range(M):
    for ma in s[i]:
        li[ma - 1].append(i)
ans = 0
for i in range(2 ** N):
    l = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for r in li[j]:
                l[r - 1] ^= 1
    if l == p:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

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

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

ans = sum(
    all(
        sum(
            t[j - 1]
            for j in range(k[i])
        ) % 2 == p[i]
        for i in range(M)
    )
    for t in product(range(2), repeat=N)
)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [[] for _ in range(N)]
for i in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        S[s - 1].append(i)
ans = 0
for bit in range(1 << N):
    den = [0] * M
    for i in range(N):
        if bit >> i & 1:
            for s in S[i]:
                den[s] += 1
    if all(d % 2 == 1 for d in den):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def on_off(upper_index, input_list): #index未満を全て切り替える
  for l in range(upper_index):
    if input_list[l] == 0:
      input_list[l] = 1
    elif input_list[l] == 1:
      input_list[l] = 0
  
  
def judge(switch_list): #1-m全ての電球が点灯するか判定. 正しければ1を返す
  count_list = [0] * m
  for k_index in range(m):
    count = 0
    for s_index in range(n):
      if switch_list[s_index] in s[k_index][1:] and switch_list[s_index] == 1:
        count += 1
    if count != 0 and count % 2 == p[k_index]:
      count_list[k_index] = 1
    else:
      break
  if 0 in count_list:
    return 0
  else:
    return 1
   
for i in range(m):
  s.append(list((int(i) for i in input().split())))
p = [int(i) for i in input().split()]

s_switch = [0] * n
count_patern = 0
i = 0
while i < n:
  count_patern += judge(s_switch)
  count_temp = 0
  for j in range(1, i+1):
    count_temp += s_switch[j-1]
    if count_temp < j:
      on_off(j, s_switch)
      if s_switch[i-1] == 1:
        i += 1
      break
print(count_patern)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M=map(int,input().split())
kslist=[]
for i in range(M):
    kslist.append(list(map(int,input().split()))) 
plist=list(map(int,input().split()))
seq=[0]*N+[1]*N
ls=list(set(list(itertools.permutations(seq,N))))
n=0
for tup in ls:
    ln=[]
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        ln.append(sum1%2)
    if ln==plist:
        n+=1
        
print(n)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M=map(int,input().split())
kslist=[]
for i in range(M):
    kslist.append(list(map(int,input().split()))) 
plist=list(map(int,input().split()))
seq=[0]*N+[1]*N
ls=list(set(list(itertools.permutations(seq,N))))
n=0
for tup in ls:
    ln=[]
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        ln.append(sum1%2)
    if ln==plist:
        n+=1
        
print(n)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
lamps = []
for i in range(M):
    lamps.append([int(x) for x in input().split()[1:]])
P = [int(x) for x in input().split()]

def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c

case = 0
for i in range(2**N):
    on = 1
    for j in range(M):
        lamps[j] = [2**(x-1) for x in lamps[j]]
        #print("i={:04b},j={},{:04b}, {}, p={}".format(i, j, i & sum(lamps[j]), popcnt0(i & sum(lamps[j]))%2, P[j]))
        if popcnt0(i & sum(lamps[j]))%2 != P[j]:
            on = 0
            break
    case += on

print(case)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


def main():
	k = []
	s = []
	answers = []

	for i in range(M + 1):
		inputs = list(map(int,input().split()))
		if i == M:
			answers = inputs.copy()
		else:
			k.append(inputs[0])
			s.append(inputs[1:])

	allCandidates = []
	for i in range(N + 1):
		candidates = [1] * i + [0] * (N - i)
		allCandidates.extend(list(itertools.permutations(candidates)))

	result = []
	for c in allCandidates:
		ok = True
		for i, ss in enumerate(s):
			sumBulk = 0
			for sNumber in ss:
				sumBulk += c[sNumber - 1]
			if sumBulk % 2 != answers[i]:
				ok = False
		if ok:
			result.append(c)

	print(len(list(set(result))))

if __name__ == '__main__':
	main()