Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

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

answer = 0
from itertools import product
for sw in product([0,1], repeat=N):
  for p, ks in zip(P,KS):
    K = ks[0]
    S = ks[1:]
    if sum([sw[s-1] for s in S])%2 != p%2:  
      break
  else:
    answer += 1
    
print(answer)

Submission status: Accepted

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


import itertools


def solve(n, m, sss, ps):
    res = 0
    for switches in itertools.product((True, False), repeat=n):
        num_on = 0
        for i in range(m):
            if sum(switches[s] for s in sss[i]) % 2 == ps[i]:
                num_on += 1
            else:
                break
        if num_on == m:
            res += 1
    return res


def main():
    n, m = (int(z) for z in input().split())
    sss = [tuple(int(x) - 1 for x in input().split())[1:] for _ in range(m)]
    ps = [int(p) for p in input().split()]
    res = solve(n, m, sss, ps)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
for switch in range(2 ** N):
    for i, ksi in enumerate(ks):
        ki = ksi[0]
        si = ksi[1:]
        #
        cnt = 0
        for j, sij in enumerate(si):
            cnt += (switch >> (sij - 1)) & 1
        #
        if cnt % 2 != p[i]:
            break
        else:
            continue
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
kk = []
ss = []
for i in range(M):
    ks = inpl()
    kk.append(ks[0])
    ss.append(ks[1:])

pp = inpl()

ans = 0
for bit in range(1<<N):
    on = [False]*N
    for b in range(N):
        if bit & (1<<b):
            on[b] = True
    for m in range(M): #電球
        k = kk[m]
        tmp = 0
        for n in range(N): # スイッチ
            if on[n] and (n+1 in ss[m]):
                tmp += 1
        if tmp%2 != pp[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

def check(status, switches, p):
    cnt = 0
    for s in status:
        if s in switches:
            cnt += 1
    return cnt % 2 == p

total = 0
for status in range(2**n):
    on = []
    for i in range(n):
        if status & 2**i:
            on.append(i+1)
    all_light = True
    for i in range(m):
        if not check(on, lights[i], ps[i]):
            all_light = False
            break
    if all_light:
        total += 1
print(total)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
sss = []
for _ in range(M):
    k, *ss = map(int, input().split())
    sss.append(ss)
ps = list(map(int, input().split()))

ans = 0
for ptn in product(range(2), repeat=N):
    numL = 0
    for ss, p in zip(sss, ps):
        numON = 0
        for s in ss:
            numON += ptn[s-1]
        if numON%2 == p:
            numL += 1
    if numL == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    inp = readnumbers()
    ii = 0

    n = inp[ii]
    ii += 1
    m = inp[ii]
    ii += 1

    S = []
    for _ in range(m):
        k = inp[ii]
        ii += 1
        S.append([x-1 for x in inp[ii:ii+k]])
        ii += k
    P = inp[ii:ii+m]

    ans = 0
    for i in range(2**n):
        switch = [int(x) for x in bin(2**(n)+i)[3:]]
        for i in range(m):
            ssum = sum(switch[j] for j in S[i])
            if ssum%2 != P[i]:
                break
        else:
            ans += 1
    print ans


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
items = []
for i in range(M):
    items.append(tuple(map(int, input().split())))
p_list = list(map(int, input().split()))

tar = []
def brute_force(s, remain):
    if remain == 0:
        tar.append(s)
    else:
        brute_force(s + "0", remain - 1)
        brute_force(s + "1", remain - 1)


brute_force("", N)

ans = 0
for T in tar:
    flag = True
    for i in range(M):
        p = p_list[i]
        k = items[i][0]
        s_list = items[i][1:]
        tmp = 0
        for s in s_list:
            t = T[s-1]
            if t == "1":
                tmp += 1
        if tmp % 2 == p:
            continue
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 6 + 10)
from collections import defaultdict




def main():
    num_switch, num_ligh = map(int, input().split())

    ligh_data = [list(map(int, input().split())) for i in range(num_ligh)]
    # print(ligh_data)
    for i in range(num_ligh):
        ligh_data[i] = ligh_data[i][1:]

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

    ans = 0

    for i in range(2 ** num_switch):
        data = list(map(int, list(bin(i)[2:])))
        data = [0 for i in range(num_switch - len(data))] + data

        flg = 1

        for j in range(num_ligh):
            kari = 0
            # print(ligh_data)
            for ele in ligh_data[j]:

                kari += data[ele - 1]
            if kari % 2 != flg_data[j]:
                flg = 0
                break

        if flg:
            ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mask = [0] * m
for i in range(m):
	l = list(map(int, input().split()))
	for x in l[1:]:
		mask[i] += 2 ** (x - 1)
p = list(map(int, input().split()))
ans = 0
cnt = [0] * (2 ** n)
for sta in range(2 ** n):
	now = sta
	while now > 0:
		cnt[sta] += now & 1
		now //= 2
	valid = True
	for i in range(m):
		if cnt[mask[i] & sta] & 1 != p[i]:
			valid = False
			break
	if valid:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    A=[int(i) for i in input().split()]
    B=A[1:]
    for b in B:
        table[b-1].add(i)
P=[int(i) for i in input().split()]
#print(table)
ans=0
for k in range(1<<N):
    U=[0]*M
    for j in range(N):
        if k&(1<<j):
            for x in table[j]:
                U[x]+=1
                U[x]%=2
    if U==P:
        ans+=1
        #print(U,k)
print(ans)

Submission status: Accepted

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 s[i]
        ) % 2 == p[i]
        for i in range(M)
    )
    for t in product(range(2), repeat=N)
)

print(ans)

Submission status: Accepted

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

bulbs = []
for i in xrange(m):
    line = map(int, raw_input().strip().split())
    bulbs.append(line[1:])

p = map(int, raw_input().strip().split())

ans = 0
for i in xrange(1 << n):
    lit = 0
    for j in xrange(m):
        l = bulbs[j]
        on = 0
        for switch in l:
            switch -= 1
            if (i & (1 << switch)): on += 1
        if (on - p[j]) % 2 == 0:
            lit += 1
    if lit == m:
        ans += 1

print ans

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
data=[]
for i in range(M):
    line=list(map(int,input().split()))
    data.append(line[1:])
P=list(map(int,input().split()))
def check(S):
    for x in range(M):
        cnt=0
        for s in data[x]:
            if S[s-1]=="1":
                cnt+=1
        if cnt%2!=P[x]:
            return False
    return True
ans=0
for i in range(pow(2,N)):
    S=bin(i)[2:]
    S="0"*(N-len(S))+S
    if check(S):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    K = []
    S = []
    for i in range(M):
        buf = input()
        buflist = buf.split()
        K.append(int(buflist[0]))
        S.append(list(map(int, buflist[1:])))
    buf = input()
    buflist = buf.split()
    P = list(map(int, buflist))
    on_pattern = 0
    for i in range(2 ** N):
        sw = []
        for j in range(N):
            sw.append(i >> j & 1 > 0)
        all_on = True
        for j in range(M):
            on_count = 0
            for x in S[j]:
                if sw[x-1]:
                    on_count += 1
            if on_count % 2 != P[j]:
                all_on = False
                break
        if all_on:
            on_pattern += 1
    print(on_pattern)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, M = read_int_array()
    bulbs = [None]*M
    for i in range(M):
        k, *switches = read_int_array()
        bulbs[i] = switches
    P = read_int_array()
    switches = []
    ans = 0
    def build(i):
        nonlocal ans
        if i == N:
            if all(sum(switches[x-1] for x in bulbs[i]) % 2 == P[i] for i in range(M)):
                ans += 1
        else:
            switches.append(False)
            build(i+1)
            switches[-1] = True
            build(i+1)
            switches.pop()
    build(0)
    write(ans)

main()

Submission status: Accepted

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

num = 0
P = list(map(int, input().split()))
for i in range(1 << N):
    tmp = [0] * M
    for j in range(N):
        if i & 1 << j:
            for l in range(M):
                if j + 1 in K[l]:
                    tmp[l] += 1

    for j in range(M):
        if tmp[j] % 2 != P[j]:
            break
    else:
        num += 1

print(num)

Submission status: Accepted

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

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

ans = 0
for i in range(2 ** N):
  for arr, p in zip(arrs, ps):
    odd = False
    for a in arr:
      if i & 1<<(a-1):
        odd = not odd
    if int(odd) != p:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  flag=True
  f=format(i,'b')
  if len(f)<n:
    f='0'*(n-len(f))+f
  for j in range(m):
    tmp=arr[j][1:]
    cnt=0
    for k in range(len(tmp)):
      if f[tmp[k]-1]=='1':
        cnt+=1
    cnt=cnt%2
    if p[j]!=cnt:
      flag=False
  if flag==True:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()

def check(N, S, P, state):
    sw = [0] * len(P)
    for i in range(N):
        if (state >> i) & 1:
            for m, s in enumerate(S):
                sw[m] += i + 1 in s
    return all((sw[i] % 2 == P[i] for i in range(len(P))))


def main():
    N, M = MI()
    S = []
    for _ in range(M):
        S.append(MIT()[1:])
    P = MIT()
    ans = 0
    for state in range(2**N):
        ans += check(N, S, P, state)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ks = []
for i in range(M):
    ks.append(list(map(int, input().split())))
p = list(map(int, input().split()))
ans = 0
for i in range(1 << N):
    f = True
    for j in range(M):
        s = 0
        for k in ks[j][1:]:
            s += (i >> (k - 1)) & 1
        if s % 2 != p[j]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

for i in range(1<<N):
    #print(i)
    for m in range(M):
        ANS2=0
        for s in S[m]:
            if i & (1<<(s-1))!=0:
                ANS2+=1

        #print(i,ANS2)
        if ANS2%2!=P[m]:
            break

    else:
        ANS+=1

print(ANS)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline

n,m = map(int,input().split())
a = []
for i in range(m):
        a.append(list(map(int,input().split())))
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
        on = [0]*n
        for j in range(n):
                if i& 1<<j:
                        on[j] = 1
        for j in range(m):
                check = 0
                for k in range(1,a[j][0]+1):
                        check += on[a[j][k]-1]
                check %=2
                if check != p[j]:
                        break
        else:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,m = LI()
    aa = [set(LI_()[1:]) for _ in range(m)]
    p = LI()
    r = 0
    for i in range(2**n):
        t = [0] * m
        for j in range(n):
            if 2**j & i:
                for k in range(m):
                    if j in aa[k]:
                        t[k] ^= 1
        if p == t:
            r += 1

    return r


print(main())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

bulbs = []

for i in range(m):
    l = input().split()
    arr = [int(x)-1 for x in l][1:]
    bulbs.append(arr)

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

import itertools

combos = 0

def test(lis):
    for i in range(m):
        need = needs[i]
        curr = 0
        for j in bulbs[i]:
            if lis[j] == 1:
                curr += 1
        if curr % 2 != need:
            return False
    return True

for i in itertools.product([0, 1], repeat=n):
    if test(list(i)):
        combos += 1

print(combos)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
s=[[int(i)-1 for i in input().split()][1:] for i in range(M)]
k=[len(i) for i in s]
p=[int(i) for i in input().split()]
t=[[] for i in range(N)]
for i in range(M):
    for j in s[i]:
        t[j].append(i)
ans=0
for seq in itertools.product([0,1],repeat=N):
    q=[0 for i in range(M)]
    for i in range(N):
        if seq[i]==1:
            for j in t[i]:
                q[j]^=1
    flag=1
    for i in range(M):
        if p[i]!=q[i]:
            flag=0
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
S=[]
for _ in range(m):
    s=list(map(int,input().split()))
    S.append(s[1:])
P=tuple(map(int,input().split()))
ans=0
for i in range(1<<n):
    for j in range(m):
        cnt=0
        for k in S[j]:
            if i&(1<<(k-1)):
                cnt+=1
        if cnt%2!=P[j]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

res = 0
for i in range(2 ** n):
        l = []
        for j in range(n):
                l.append(int((i & (2 ** j)) == 0))
        flag = True

        for ll, j in enumerate(k):
                cnt = 0
                for q in j:
                        cnt += l[q - 1]
                if cnt % 2 != p[ll]:
                        flag = False

        if flag:
                res += 1
print(res)

Submission status: Accepted

Solution code:
import sys

n, m = list(map(int, input().split()))
swi = []
for _ in range(m):
    k, *sss = list(map(int, input().split()))
    t = 0
    for s in sss:
        t += 1 << (s - 1)
    swi.append(t)
ppp = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    for s, p in zip(swi, ppp):
        t = i & s
        c = bin(t).count('1') % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)

Submission status: Runtime Error

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

ans=0
for i in range(1<<n):
  for k in range(m):
    sw=0
    for j in range(n):
      if (i>>j)&1==0 and j+1 in S[k]:
        sw+=1
    if se%2!=p[k]:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

ans=0
for i in range(1<<n):
  for k in range(m):
    sw=0
    for j in range(n):
      if (i>>j)&1==0 and j+1 in s[k]:
        sw+=1
    if se%2!=p[k]:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

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

# calc
# bit full search
ans = 0 
for i in range(2**n):
    tmp = i 
    sw = []
    if i == 0:
        sw = [0] 
    while tmp > 0:
        sw.append(tmp&1)
        tmp = tmp>>1
    while len(sw) < n:
        sw.append(0)

    #print('sw =', sw)
    
    # check whether current sw satisfies the condision.
    ok = True
    # light bulb j
    for j in range(m):
        tmp = 0 
        for a in range(k[j]):
            tmp += sw[a+1]
        if tmp%2 != p[j]%2:
            ok = False
            break
    if ok: 
        # print('sw =', sw)
        ans += 1

print(ans)

Submission status: Runtime Error

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

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

# calc
# bit full search
ans = 0 
for i in range(2**n):
    tmp = i 
    sw = []
    if i == 0:
        sw = [0] 
    while tmp > 0:
        sw.append(tmp&1)
        tmp = tmp>>1
    while len(sw) < n:
        sw.append(0)

    #print('sw =', sw)
    
    # check whether current sw satisfies the condision.
    ok = True
    # light bulb j
    for j in range(m):
        tmp = 0 
        for a in range(k[j]):
            tmp += sw[a+1]
        if tmp%2 != p[j]%2:
            ok = False
            break
    if ok: 
        print('sw =', sw) 
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration
    
    
def main():
    N, M = MI()
    Switch = [LI()[1:] for i in range(N)]
    P = LI()
    result = 0
    for i in range(2**N):
        temp = [0]*M
        for j in range(N):
            if i>>j & 1 != 0:
                for k in Switch[j]:
                    temp[k-1] += 1
        result += 1
        for num1, num2 in zip(temp, P):
            if num1 % 2 != num2:
                result -= 1
                break
    print(result)
            
        
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))
ans = 0
sw = [False]*m                # 各電球の点灯リストを作成
for j in range(m):            # 各電球について
    cnt = 0
    for k in range(1,len(s[j])):   # 各電球のswitchについて
        if i>>s[j][k]-1&1:
            cnt += 1
    if cnt%2==p[j]:
        sw[j]=True
if all(sw):
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))ans = 0
for i in range(1<<n):             # 全switch(n)のon/offパターン数
    sw = [False]*m                # 各電球の点灯リストを作成
    for j in range(m):            # 各電球について
        cnt = 0
        for k in range(1,len(s[j])):   # 各電球のswitchについて
            if i>>s[j][k]&1:
                cnt += 1
        if cnt%2==p[j]:
            sw[j]=True
    if all(sw):
        ans+=1
print(ans)