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()))
s = []
ans = 0
for _ in range(M):
    temp = list(map(int, input().split()))
    s.append(temp[1:])
p = list(map(int, input().split()))
for i in range(2 ** N):
    flag = 1
    flag_1 = 1
    sw = bin(i)[2:]
    sw = sw.zfill(N)
    for j in range(M):
        sumsw = 0
        for k in s[j]:
            sumsw += int(sw[k-1])
        if sumsw % 2 != p[j]:
            flag = 0
            flag_1 = 0
            break
        if flag_1 == 0:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [[int(i) for i in input().split(" ")] for i in range(m)]
p = [int(i) for i in input().split(" ")]
c = 0
for i in range(2**n):
    t = bin(i+2**n)[2:]
    a = sum([0 if sum([1 if t[l]=="1" else 0 for l in k[j][1:]])%2 == p[j] else 1 for j in range(len(k))])
    if a == 0:
        c+=1
print(c)

Submission status: Accepted

Solution code:

import numpy as np
N, M = map(int, raw_input().split())
k = np.empty(M, dtype=int)
s = []
for i in xrange(M):
    inp = map(int, raw_input().split())
    k[i] = inp[0]
    s.append(np.array(inp[1:])-1)

is_odd = np.array(map(int, raw_input().split()), dtype=bool)

ans = 0
for i in xrange(2**N):
    all_lighted = True
    on = np.array([int(k) for k in"{:0{}b}".format(i,N)])
    for j in xrange(M):
        if not np.sum(on[s[j]]) % 2 == is_odd[j]:
            all_lighted=False
            break
    if not all_lighted:
        continue
    ans += 1

print ans

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = []
for i in range(2**n):
    x.append(format(i, '011b'))
y = []
for _ in range(m):
    _, *s = map(int, input().split())
    y.append(s)
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    f = 0
    for j in range(m):
        cnt = 0
        for k in y[j]:
            cnt += int(x[i][k - n - 1])
        if cnt % 2 == p[j]:
            f += 1
    if f == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools


def main():
    N,M = map(int,input().split())
    S={}
    P=[0] * (M+1)
    List=[]
    for i in range(1,M+1):
        array = list(map(int, input().split()))
        for s in range(1,len(array)):
            
            if i in S.keys():
                S[i].append(array[s])
            else:
                S[i]=[]
                S[i].append(array[s])

    array = list(map(int, input().split()))
    for i in range(1,M+1):
        P[i]=array[i-1]

    for i in range(N):
        List.append(i+1)

    comb=[]
    count=0
    for i in range(1,N+1):
        for l in itertools.combinations(List,i):
            comb=l       
            flag=-1
            for j in range(1,M+1):
                
                cnt=0
                for k in range(0,len(comb)):
                    if comb[k] in S[j]:
                        cnt+=1
                if cnt%2==P[j]:
                    flag=1
                else:
                    flag=-1
                    break
            if flag==1:
                count+=1

    for j in range(1,M+1):
        if(0==P[j]):
            flag=1
        else:
            flag=-1
            break
    if flag==1:
        count+=1
        
    print(count)
                    
                               
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
import numpy as np
import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def main():
    n,m=inpm()
    s=inpll(m)
    p=inpl()
    k=[]
    cnt = 0
    for i in range(m):
        k.append(s[i][0])
        s[i].pop(0)
    
    for i in range(n+1):
        for lis in combinations(range(n),i):
            a = [0 for _ in range(n)]
            for j in lis:
                a[j] = 1
            key = 0
            for den in range(m):
                b = [0 for _ in range(n)]
                for con in s[den]:
                    b[con-1]=1
                a=np.asarray(a)
                b=np.asarray(b)
                x = np.dot(a,b)
                if x%2 != p[den]:
                    key = 1
                    break
            if key == 0:
                cnt+=1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M= map(int,input().split(' '))
KSn =[]
for _ in range(M):
    KS = list(map(int,input().split(' ')))
    K = KS[0]
    Sn = KS[1:K+1]
    KSn.append(Sn)
Pn = list(map(int,input().split(' ')))

def bit_cal2(n):
    return_list = ['']* (2 ** n)
    for i in range(2 ** n):
        for j in range(n):
            if ((i >> j) & 1):
                return_list[i] = return_list[i] + '1'
            else:
                return_list[i] = return_list[i] + '0'
    return return_list

possible_list = bit_cal2(N)
comb_count = 0
for possible in possible_list:
    flag = True
    for i in range(M):
        count = 0
        for i2 in KSn[i]:
            count += int(possible[i2-1])
        if count%2 != Pn[i]:
            flag = False
            break
    if flag:
        comb_count += 1
print(comb_count)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
X=[]
for i in range(M):
  X+=[[int(x) for x in input().split()]]
P=[int(x) for x in input().split()]
result=0
for switch in itertools.product([0,1],repeat=N):
  on=0
  for i in range(M):
    count=0
    for j in range(X[i][0]):
      if switch[X[i][j+1]-1]==1:
        count +=1
    if count%2==P[i]:
      on +=1
    else:
      break
  if on==M:
    result +=1
print(result)

Submission status: Accepted

Solution code:
# bit演算
N, M = map(int, input().split())
# 各スイッチがどの電球に繋がっているかをbitで持つ
# スイッチ1が電球1、電球2に繋がっている場合は
# 101 -> 5 という持ち方
a = [0] * N
for i in range(M):
    K, *S = list(map(int, input().split()))
    for j in range(K):
        s = S[j]
        s -= 1
        # s番目のスイッチにi番目の電球が繋がっている
        a[s] |= 1 << i

expected = 0
l = list(map(int, input().split()))
for i in range(M):
    expected |= l[i] << i

# on/offの2通り、スイッチは最大10個なので、# 2^10=1024で全通り試してもOK
# on/offの全ての組み合わせをbitでループする
ans = 0
for s in range(1 << N):
    # 各電球の状態(bit)
    lighting = 0
    for i in range(N):
        # iビット目が立っているか
        if s >> i & 1:
            # スイッチを押して、つながった電球の状態を反転させる
            lighting ^= a[i]
    # 各スイッチを押した後の電球の状態が理想と一致するか
    if lighting == expected:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    ks = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    p = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    for v in itertools.product([True, False], repeat=n):
        b = True
        for i in range(m):
            t = 0
            for kv in ks[i][1:]:
                t += v[kv-1]
            if t % 2 != p[i]:
                b = False
                break
        if b:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# N, M<=10なので全探索の気持ちが生える
# -> N個のスイッチについて0,1のすべての状態を想定し、
#   それぞれについてみたとき、各電球が条件を満たしているか都度判断する

n, m = map(int, input().split())
balbs = [[] for _ in range(m)]
for i in range(m):
    # zero order
    connectswtiches = list(map(lambda x: int(x) - 1, input().split()))[1:]
    balbs[i] = connectswtiches

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

# 2^N
def f(cur, n):
    if n == 0:
        # 判定
        for i, balb in enumerate(balbs):
            on_switch_count = 0
            for swtich_n in balb:
                if cur[swtich_n] == 1:
                    on_switch_count += 1
            if correct_state[i] != on_switch_count % 2:
                return 0
        return 1

    ret = 0
    lnh = len(cur)
    nex = cur[:]
    nex[lnh - n - 1] = 1
    ret += f(nex, n - 1)
    nex[lnh - n - 1] = 0
    ret += f(nex, n - 1)
    return ret


print(f([0 for _ in range(n)], n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()] #Nがスイッチの数、Mは電球の数
kslist = []
for i in range(M):
    kslist.append([int(i)-1 for i in input().split()][1:])
plist = [int(i) for i in input().split()]

#print(kslist)
#print(plist)

count = 0

lamp_str = "0"*N
for i in range(2**N):
    lamp_onoff_list = [int(i) for i in lamp_str]
    iflampturnson = [0 for i in range(M)]
    for j in range(M):
        for s in kslist[j]:
            iflampturnson[j] += lamp_onoff_list[s]
    #print(lamp_onoff_list,iflampturnson)
    iflampturnson = [k%2 for k in iflampturnson]
    
    buff = True
    for k in range(M):
        if plist[k] != iflampturnson[k]:
            buff = False
    if buff == True:
        count += 1

    lamp_str = format(int(lamp_str,2) + 1,"b")
    lamp_str = lamp_str.zfill(N)

print(count)

Submission status: Accepted

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

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

for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1,len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Submission status: Accepted

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

lights = []
for _ in range(M):
    S = list(map(int, input().split()))
    mask = 0
    for a in S[1:]:
        mask |= (1 << (a - 1))
    lights.append(mask)

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

ans = 0
for mask in range(1 << N):
    for state, p in zip(lights, P):
        cnt = 0
        for d in range(N):
            if ((1 << d) & state) > 0 and ((1 << d) & mask) > 0:
                cnt += 1
        if cnt % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]
odd_even = list( map(int,input().split()))
counter = 0
for i in range(2**n):
    switches = ["off"] * n
    num1 = 0
    for j in range(n):
        if (i>>j)&1:
            switches[n-j-1] = "on"
    for i in range(m):
        # numは条件に当てはまる電球の点灯数
        num = 0
        for k in range(1,len(li[i])):
            if switches[li[i][k]-1] == "on":
                num += 1
        if num % 2 == odd_even[i]:
            num1 += 1
            continue
        else:
            break
    if num1 == m:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n): # bitで全状態を列挙
    for j in range(m): # あるスイッチ状態における各電球のONOFFを探索する
        count = 0
        #print(i, (i>>j)&1)
        for k in range(n):
            if ((i >> k) & 1) and (k+1) in l[j][1:]:
                # j番目の電球にスイッチkがつながっていたらcountを追加
                count += 1
        if count % 2 != p[j]:
            break
        if j == m-1: ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
b=list(map(int,input().split()))
ans=0
for i in range(2**n):
  c=[]
  q=True
  for j in range(n):
    c.append((i>>j)&1)
  for k in range(m):
    p=0
    for l in range(1,a[k][0]+1):
      if c[a[k][l]-1]==1:
        p+=1
    if p%2!=b[k]:
      q=False
  if q:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
light = []
for _ in range(M):
    light.append(list(map(int,input().split())))
p = list(map(int,input().split()))
ans = 2 ** N
for i in range(2 ** N):
    tmp = [0] * N
    for k in range(N):
        if 1 & i>>k:
            tmp[k] = 1
    for k in range(M):
        count = 0
        for l in range(1,light[k][0]+1):
            if tmp[light[k][l]-1] == 1:
                count += 1
        if count % 2 != p[k]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(2, [[1, 2], [2]], [0, 1]), 1)

    def test_2(self):
        self.assertEqual(think(2, [[1, 2], [1], [2]], [0, 0, 1]), 0)

    def test_3(self):
        self.assertEqual(think(5, [[1, 2, 5], [2, 3]], [1, 0]), 8)


def solve():
    n, s, p = read()
    result = think(n, s, p)
    write(result)


def read():
    n, m = read_int(2)
    s = []
    for _ in range(m):
        buf = read_line().split()
        k = int(buf[0])
        s.append(list(map(int, buf[1:k + 1])))
    p = read_int(m)
    return n, s, p


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, s, p):
    count = 0
    m = len(s)
    for bit in range(2 ** n):
        satisfy = True
        for i in range(m):
            if satisfies_condition(bit, s[i], p[i]):
                continue
            satisfy = False
            break
        if satisfy:
            count += 1
    return count


def write(result):
    print(result)


def satisfies_condition(bit, s, p):
    result = 0
    for ss in s:
        result ^= mask(bit, ss)
    return result == p


def mask(bit, k):
    return (bit >> (k - 1)) & 1


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
S = []
for _ in range(m):
    *a, = map(int, input().split())
    l = a[1:]
    S.append(l)
*p, = map(int, input().split())

ans = 0
for i in range(2**n):
    tmp = np.array([i >> j & 1 for j in range(n)])
    if p == [sum(tmp[np.array(s)-1]) % 2 for s in S]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = []
K = []
for i in range(M):
    s = list(map(int,input().split()))
    k = s.pop(0)
    S.append(s)
    K.append(k)
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    sw = [0]*N
    for j in range(N):
        if (i>>j)&1:
            sw[j] = 1
    flag = 1
    for m in range(M):
        po = S[m]
        sum = 0
        for k in range(K[m]):
            if sw[po[k]-1] == 1:
                sum = (sum + 1)%2
        if P[m] != sum:
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
gp = [['0' for _ in range(N)] for _ in range(M)]
for i in range(M):
    ksl = list(map(int, input().split()))
    for s in ksl[1:]:
        gp[i][N-s] = '1'
for i in range(M):
    gp[i] = ''.join(gp[i])
pl = list(map(int, input().split()))
res = 0
for sw in range(2**N):
    for i,g in enumerate(gp):
        ing = int(g, 2)
        swing = sw & ing
        #print("sw:%d, ing:%d, swing:%d"%(sw, ing, swing))
        fsw = format(sw, 'b').zfill(N)
        fing = format(ing, 'b').zfill(N)
        fswing = format(swing, 'b').zfill(N)
        #print("fsw:%s, fing:%s, fswing:%s"%(fsw, fing, fswing))
        if fswing.count('1') % 2 != pl[i]:
            break
    else:
        #print(fsw)
        res += 1
print(res)

Submission status: Accepted

Solution code:
# 2019-11-13 21:06:16(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    
    on_off_patterns = [''.join(pattern) for pattern in itertools.product('01', repeat=n)]
    
    bulbs = [[int(x) for x in sys.stdin.readline()[1:].split()] for _ in range(m)]
    p = [int(x) for x in sys.stdin.readline().split()]

    combinations = 0
    for i in range(2**n):
        pattern = on_off_patterns[i]
        for j in range(m):
            switches = bulbs[j]
            on_count = 0
            for switch in switches:
                if pattern[switch-1] == '1':
                    on_count += 1
            if on_count % 2 == p[j]:
                continue
            else:
                break
        else:
            combinations += 1
    
    print(combinations)
    
    # enumerate on/off-patters by using binary number.


if __name__ == "__main__":
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    s = []
    mod = []
    ans = 0

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

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

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

        all = 0
        for i in range(M):
            li = s[i]
            total = 0
            for item in li:
                total += switch[item-1]

            if mod[i] != total % 2:
                break
            else:
                all += 1

        if all == M:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    s=[[]]*M
    for i in range(M):
        l=list(map(int,input().split()))
        s[i]=list(map(lambda x: x-1, l[1:]))
    p=list(map(int,input().split()))
    ans=0
    for i in range(2**N):
        c = [0]*M
        for j in range(N):
            if (i >> j) & 0b1 == 1:
                for light_num in range(M):
                    if j in s[light_num]:
                        c[light_num]+=1
        for light_num in range(M):
            if p[light_num] == c[light_num]%2:
                pass
            else:
                break
        else:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    bit = str(bin(i))[2:].zfill(N)
    for (_, *s), p in zip(KS, P):
        ons = 0
        for si in s:
            ons += int(bit[si-1])
        if ons % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def p_c():
    n, m = map(int, input().split())
    s = [list(map(int, input().split()))[1:] for _ in range(m)]
    *p, = map(int, input().split())
    b = []
    for _s in s:
        bit = 0
        for i in _s:
            bit += (1 << (i - 1))
        b.append(bit)
    ans = 0
    for i in range(1 << n):
        for j, k in enumerate(b):
            if bin(i & k).count("1") & 1 != p[j]:
                break
        else:
            ans += 1
    print(ans)
    
p_c()

Submission status: Accepted

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

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

pl = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    bit = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            bit[j] = 1
    
    for idx, ks in enumerate(ksl):
        p = 0
        for k in ks:
            p += bit[k-1]
        if p % 2 != pl[idx]:
            break
    else:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
""" AtCoder """
import itertools

n, m = (int(_) for _ in input().split())
sk = []
for _ in range(m):
    sk.append([int(__) for __ in input().split()][1:])
p = [int(_) for _ in input().split()]
ans = 0

for s in itertools.product([0,1], repeat=n):
    check = True
    for i, ski in enumerate(sk):
        skt = 0
        for skj in ski:
            skt += s[skj-1]
        if skt%2 != p[i]:
            check = False
            break

    if check == True:
        ans += 1

print(ans)

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
bi="1"*n
for i in range(int(bi,2)+1):
    c="0"*(n-len(bin(i))+2)+bin(i)[2:]
    #ここで1つ1つの電球に注目
    for j in range(m):
        sum=0
        for l in range(ks[j][0]):
            sum+=int(c[ks[j][l+1]-1])
        if sum%2!=p[j]:
            break
        if j==m-1:
            ans+=1
print(ans)

Submission status: Accepted

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


def make_mask(n, switch_indices):
    ans = [0 for _ in range(n)]
    for index in switch_indices:
        ans[index-1] = 1
    ans_int = 0
    for i in range(n):
        if ans[i] == 1:
            ans_int += 2 ** i
    return ans_int


masks = []
for s_i in s:
    masks.append(make_mask(n, s_i))


c = 0
for i in range(2 ** n):
    state = str(bin(i))
    is_all_on = True
    for j in range(m):
        result = i & masks[j]
        if p[j] != str(bin(result)).count("1") % 2:
            is_all_on = False
            break
    if not is_all_on:
        continue
    c += 1
print(c)

Submission status: Accepted

Solution code:
tmp = list(map(int, input().split()))
n = tmp[0]
m = tmp[1]

k = [[0] for i in range(n+1)]
s = [[]  for i in range(n+1)]
for i in range(m):
  tmp = list(map(int, input().split()))
  k[i] = tmp[0]
  for j in range(1,k[i]+1):
    s[i].append(tmp[j])

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

ans = 0
for cnt in range(0, 2**n):
  for i in range(m):
    on = 0
    light = True
    for sw in s[i]:
      if (cnt // (2**(sw-1))) % 2 == 1:
        on += 1
#    print('CNT=' + str(cnt) + ' ON=' + str(on))
    if on%2 != p[i]:
      light = False
      break
  if light:
    ans += 1

print (ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
L=[]
for i in range(m):
    l=list(map(int,input().split()))
    s=0
    for j in range(l[0]):
        s+=2**(l[j+1]-1)
    L.append(s)
P=list(map(int,input().split()))
r=0
for i in range(1<<n):
	p=0
	for j in range(m):
		if bin(i&L[j]).count('1')%2==P[j]:
			p+=1
	if p==m:
		r+=1
print(r)

Submission status: Accepted

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N, M = map(int, input().split())
    SW = [list(map(int, input().split()))[1:] for _ in range(M)]
    P = list(map(int, input().split()))

    num = 0
    for i in range(2**N):
        ng = False
        for j, sw in enumerate(SW):
            n = 0
            for k in sw:
                if i & 2**(k-1):
                    n = n + 1
            if n%2 != P[j]:
                ng = True
                break
        else:
            num = num + 1
    
    print(num)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc128","c",main)

Submission status: Accepted

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

for i in range(2**n):
    pattern=format(i,"b").zfill(n)
    point=0
    
    for j in range(m):
        swi=0
        for k in s[j]:
            if pattern[k-1]=="1":
              swi +=1
        if swi%2==p[j]:
          point +=1
    if point==m:
      cnt +=1
      
print(cnt)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    n,m=map(int,input().split())
    kk=[]
    sss=[]
    for _ in range(m):
        k,*ss=map(int,input().split())
        kk.append(k)
        sss.append(ss)
    pp=list(map(int,input().split()))
    c=0
    for i in range(2**n):
        if all(sum((i >> (s-1))&1 for s in ss)&1==p for p,ss in zip(pp,sss)):
            c += 1
    print(c)

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[] for i in range(N)]
for i in range(M):
    a = [int(j) for j in input().split()]
    for v in a[1:]:
        D[v - 1].append(i)

P = [int(i) for i in input().split()]
ans = 0
for i in range(1 << N):
    S = [0] * M #各電球が何回スイッチ入ってるか
    for k in range(N):
        if ((i >> k) & 1) == 1:
            for d in D[k]:
                S[d] ^= 1

    if all([s == p for  s,p in zip(S, P)]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[] for i in range(N)]
for i in range(M):
    a = [int(j) for j in input().split()]
    for v in a[1:]:
        D[v - 1].append(i)

P = [int(i) for i in input().split()]
ans = 0
for i in range(1 << N):
    S = [0] * M #各電球が何回スイッチ入ってるか
    for k in range(N):
        if ((i >> k) & 1) == 1:
            for d in D[k]:
                S[d] += 1

    if all([(s % 2) == p for  s,p in zip(S, P)]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
k,s=[],[]
ans=0
for i in range(m):
    kk,*tmp=[int(j) for j in input().split()]
    k.append(kk)
    s.append(tmp)
p=[int(i) for i in input().split()]

for bit in range(1<<n):
    pattarn = []
    for j in range(n):
        if (bit & (1<<j)):
            pattarn.append(j)
    flg=True
    for i in range(m):
        cnt=0
        for j in range(k[i]):
            if s[i][j]-1 in pattarn:
                cnt+=1
        if cnt%2!=p[i]:
            flg=False
    if flg:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
for i in range(m):
  s.append(list(map(int, input().split())))
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
  flg = True
  for j in range(m):
    on_cnt = 0
    for k in range(1, s[j][0]+1):
      if (i >> s[j][k] - 1)&1:
        on_cnt += 1
    if on_cnt % 2 != p[j]:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Accepted

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

    ans = 0
    for i in range(2**n):
        binary = bin(i)
        binary = binary[2:].zfill(n)
        binary_list = [int(x) for x in binary]
        for j in range(m):
            temp = 0
            for k in range(array[j][0]):
                switch = array[j][k+1]
                temp += binary_list[switch-1]
            if temp%2 != P[j]:
                break
            if j == m-1:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

switch = []
for i in range(2**n):
    x = bin(i)
    switch.append(['0']*(n+2-len(x))+list(x)[2:])
    
ans = 0

for i in switch: #各スイッチパターン
    ite = 0
    for j in S: #各電球
        count = 0
        for k in j:
            count += int(i[k-1])
        if count%2 != P[ite]:
            break
        else:
            ite += 1
    if ite == len(S):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

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

k = [-1]*m
s = [-1]*m
for i in range(m):
  tmp = input().split()
  k[i] = int(tmp[0])
  s[i] = map(int, tmp[1:])
  s[i] = [si-1 for si in s[i]]

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

#print(s)

def check(switch):
  #print("sw", switch)
  tmp = [sum([1 for j,sw in enumerate(switch) if (sw==1) and (j in s[i])])%2 for i in range(m)]
  #print("tmp", tmp)
  if tmp==p:
    return 1
  else:
    return 0

def dp(switch, idx):
  count=0
  if idx==n:
    return check(switch)
  else:
    count += dp(switch+[0], idx+1)
    count += dp(switch+[1], idx+1)
    return count

switch = []
idx = 0
count = 0
count = dp(switch, idx)
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
S=[list(map(int,input().split()))[1:] for i in range(m)]
P=list(map(int,input().split()))
cnt=0
for i in range(2**n):
    pattern=format(i,"b").zfill(n)
    point=0
    for j in range(m):
        swi=0
        for k in S[j]:
            if pattern[k-1]=="1":swi +=1
        if swi%2==P[j]:point +=1
    if point==m:cnt +=1
print(cnt)