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()))
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 bit in range(1<<n):
    for s,p in zip(swi,ppp):
        t = bit & s
        c = bin(t).count("1") % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    on = []
    for j in range(n):
        if((i >> j) & 1):
            on.append(1)
        else:
            on.append(0)
    count = 0
    for j in range(m):
        total = 0
        for k in range(s[j][0]):
            if on[s[j][k+1]-1] == 1:
                total += 1
    
        if total % 2 == p[j]:
            count += 1
    if count == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# C - Switches

N, M = map(int, input().split())
switches = []
for _ in range(M):
    k, *s = map(int, input().split())
    switches.append([i - 1 for i in s])
lights = [int(p) for p in input().split()]

def f(i, on_off):
    if N <= i:
        result = 1
        for i in range(M):
            on = 0
            for j in switches[i]:
                on += on_off[j]
            if on % 2 != lights[i]:
                result = 0
        return result
    return f(i + 1, on_off + [1]) + f(i + 1, on_off + [0])

print(f(0, []))

Submission status: Accepted

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

n, m = LI()
ks = [LI() for _ in range(m)]
p = LI()

count_total = 0

for i in range(2**n):
    bit = [(i>>j)&1 for j in range(n)]
    failed = False
    for k in range(m):
        kx = ks[k][0]
        count_on = 0
        for l in range(1, kx + 1):
            skl = ks[k][l]
            count_on += bit[skl - 1]
        if count_on % 2 != p[k]:
            failed = True
    if not failed:
        count_total += 1

print(count_total)

Submission status: Accepted

Solution code:


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

res = 0
def dfs(i, now):
    global res
    if i == N:
        for j in range(M):
            cnt = 0
            for s in range(k_s[j][0]):
                cnt += now[k_s[j][s+1]-1]
            if cnt % 2 != p[j]:
                break
            if j == M - 1:
                res += 1
    else:
        dfs(i+1, now + [0])
        dfs(i+1, now + [1])

dfs(0, [])

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 18:40:35 2020

@author: Kanaru Sato
"""

n,m = list(map(int,input().split()))
slist = [[] for i in range(m)]
for i in range(m):
    _ = list(map(int,input().split()))
    for j in range(len(_)-1):
        slist[i].append(_[j+1]-1)
p = list(map(int,input().split()))

ans = 0
for state in range(2**n):
    Allbright = 1
    for light in range(m):
        count = 0
        for switch in range(n):
            if switch in slist[light]:
                count += (state&(1<<switch))>>switch
        if count%2 != p[light]%2:
            Allbright = 0
            break
    if Allbright == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
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 bit in range(1<<n):
    for s,p in zip(swi,ppp):
        t = bit&s
        c = bin(t).count("1") % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

#n,m = 10,10
#a = [[4, 6, 3, 7, 5], [3, 1, 10, 5], [4, 8, 7, 1, 2], [5, 5, 10, 2, 7, 8], [6, 3, 1, 6, 8, 2, 5], [5, 6, 10, 7, 1, 3], [4, 3, 5, 7, 6], [4, 3, 9, 7, 5], [4, 3, 6, 5, 7], [4, 2, 7, 1, 8]]
#p = [0, 0, 1, 1, 1, 0, 0, 0, 0, 1]

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

    for k in range(0,a[j][0]):
      #print(a[j][k+1]) 番目のスイッチをチェック
      count += i>>(a[j][k+1]-1) & 1

    if count%2 != p[j]:
      ck = False
      break
  if ck:
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
in_M =[[]]*M 
for m in range(M):
    in_M[m] = list(map(int,input().split()))
out_M = list(map(int,input().split()))

all_on_cnt = 0
for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if((i>>j) & 1): # iをj回右シフトさせ末尾をみる
            switch[j] = 1
    
    for j in range(M):
        total = 0
        for l in range(1,in_M[j][0]+1):
            total += switch[in_M[j][l]-1]
        if total%2 != out_M[j]:
            break
    else:
        all_on_cnt += 1
          
print(all_on_cnt)

Submission status: Accepted

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

ans=0
for i in range(2**N):
  bit=format(i,'0'+str(N)+'b')
  bit=list(map(int,bit))
  on=0
  for s,p in zip(S,P):
    check=0
    for j in s:
      j-=1
      check+=bit[j]
    if check%2==p:on+=1
  if on==M:ans+=1  
print(ans)

Submission status: Accepted

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

lamp = []
# 一つのランプがどのスイッチにつながっているかをビットで表す
for i in range(m):
    k, *tmp = map(int, input().split())
    mask = 0
    for j in tmp:
        mask += 1 << (j-1)
    lamp.append(mask)

# １つのランプ毎に活性するときのスイッチON数の偶奇の取得
p = list(map(int, input().split()))

# スイッチの活性／非活性ケースごとに全ランプがＯＮになっているかチェック
# スイッチの活性／非活性ケースごと
ans = 0
for i in range(1<<n):
    all_on = True
    # ランプごと
    for j in range(len(lamp)):
        if not bin(i & lamp[j]).count('1') % 2 == p[j]:
            all_on = False
            break
    if all_on:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

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

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

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

st = list(product([0,1],repeat=N))

ans = 0

for i, s in enumerate(st):
    tmp = []
    for j, sw in enumerate(switch):
        on = 0
        for x in sw:
            on += s[x-1]
        if (on%2)==p[j]:
            tmp.append(True)
        else:
            tmp.append(False)
    if all(tmp)==True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={}
for i in range(m):
  d[i]=tuple(map(int,input().split()))[1:]
p=tuple(map(int,input().split()))
ans = 0
for i in range(2**n):
  cnt=[0]*n
  num = 0
  for j in range(n):
    if (i>>j)&1:
      cnt[j]=1
  for i in range(m):
    tmp = 0
    v=d[i]
    for s in v:
      if cnt[s-1]==1:
        tmp += 1
    if tmp%2==p[i]:
      num += 1
  if num == m:
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

#READ INPUT
N,M = map(int,input().split())
switches = list()
for i in range(M):
    curSwitch = [int(temp) for temp in input().split()] #read as list
    switches.append(curSwitch[1:])

p = [int(p) for p in input().split()]

#iterate through each possible combination of switches
numValidComb=0
for i in range(2**N):
    bit = [(i>>j)&1 for j in range(N)]
    numActiveBulb = 0
    for curBulb in range(M):
        curS = switches[curBulb]
        curP = p[curBulb]
        
        ind = [x-1 for x in curS]
        activeSwitch = [bit[this] for this in ind]

        if (sum(activeSwitch)%2 == curP):
            numActiveBulb+=1
    
    if (numActiveBulb==M):
        numValidComb+=1
        
print(numValidComb)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 128 C - Switches

import sys

N, M = map(int, sys.stdin.readline().strip().split())

S = [[0] * N for _ in range(M)]
for i in range(M):
    _, *s = map(int, sys.stdin.readline().strip().split())
    for j in s:
        S[i][j-1] = 1
p = list(map(int, sys.stdin.readline().strip().split()))

ans = 0
for i in range(2 ** N):
    bit = [(i >> j) & 1 for j in range(N)]
    for i, s in enumerate(S):
        o_e = sum([x * y for x, y in zip(s, bit)]) % 2
        if o_e != p[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
ks = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    sw = []
    for _ in range(M):
        k, *S = map(int, readline().split())
        sw.append(S)
    p = list(map(int, readline().split()))

    cnt = 0
    for i in range(2**N):
        jtmp = []
        flag = True
        for j in range(N):
            if (i>>j)&1:
                jtmp.append(j+1)
        
        for k in range(M):
            setj = set(jtmp)
            settmp = set(sw[k])
            if len(setj&settmp)%2 != p[k]:
                flag = False
                break
        if flag:
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    S = [[]]*M
    for i in range(M):
        S[i] = list(map(int, input().split()))
    P = list(map(int, input().split()))
    LUMP, COMB = 0, 0
    for bit in range(1<<N):
        LUMP = 0
        for j in range(M):
            on = 0
            for k in range(1, S[j][0]+1):
                if bit>>(S[j][k]-1) & 1:
                    on += 1
            if on%2 == P[j]:
                LUMP += 1        
        if LUMP == M:
            COMB  += 1
    print(COMB)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(2 ** n):
    is_on = True
    for j in range(m):
        k = swtiches[j][0]
        s = swtiches[j][1:]
        cnt = 0
        for si in s:
            if i >> (si - 1) & 1:
                cnt += 1
        if cnt % 2 != p[j]:
            is_on = False
    if is_on:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
M = []
for i in range(m):
    ks = LI()
    mask = 0
    for s in ks[1:]:
        mask += 1 << (s-1)
    M.append(mask)
P = LI()


ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & M[i]).count("1") % 2 != P[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

N , M = map(int,input().split())
data = []
[data.append(list(map(int,input().split()))) for _ in range(M)]
P = list(map(int,readline().rstrip().split()))

ans = 0
for x in range(2 ** N):
    bi = bin(x)[2::][::-1]
    on = [0] * N
    flag = 1
    for index , b in enumerate(bi) :
        if b == "1":
            on[index] = 1
    for index , d in enumerate(data) :
        num_sw = 0
        for s in d[1::]:
            num_sw += on[s-1]
        if P[index] != (num_sw % 2):
            flag = 0
            break
    if flag == 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)]
target = list(map(int,input().split()))

#n,m = 2,3
#a = [[2,1,2], [1,1],[1,2]]
#target = [0,0,1]

ans = 0
s = [0] * n
for i in range(2**n):
  x = format(i,'b').zfill(n)

  for num,j in enumerate(x):
    s[num] = int(j)

  ck = 1
  for num,alist in enumerate(a):
    count = 0
    for j in range(1,alist[0]+1):
      count += s[alist[j]-1]
    if(count%2 != target[num]):
      ck = 0
  ans += ck

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

ans = 0
for i in range(2**N):
    A = [0]*M #スイッチの状態
    for j in range(N):
        if (i >> (N-j-1))&1:
            for k in range(M):
                if j+1 in lamp_switch[k]:
                    A[k] += 1
                    A[k] %= 2
    if pattern == A:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1<<N):
    light = [0 for k in range(M)]
    flag = [False for k in range(N)]
    for j in range(N):
        if (i>>j & 1) == 1:
            flag[j] = True
    for j in range(M):
        for k in KS[j][1:]:
            light[j] += 1 if flag[k-1] else 0
            light[j] = light[j]%2
    if light == p:
        ans += 1
print(ans)

Submission status: Accepted

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

switch = []
for i in range(m):
    k, *tmp = map(int, input().split())
    switch_mask = 0
    for j in tmp:
        switch_mask += 1 << (j-1)
    switch.append(switch_mask)

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

ans = 0
for i in range(1 << n):
    all_on = True
    for j in range(len(switch)):
        if not bin(i & switch[j]).count('1') % 2 == p[j]:
            all_on = False
            break
    if all_on:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Lamp_switch = []
for _ in range(M):
    S = list(map(int, input().split()))[1:]
    Lamp_switch.append(S)
 
Pon = list(map(int, input().split()))
ans = 0

for i in range(2**N):
  Cou = [0]*M
  for j in range(N):
    if (i>>j)&1:
      for k in range(M):
        if (j+1) in Lamp_switch[k]:
          Cou[k] += 1
          Cou[k] %= 2
  if Cou == Pon:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        k, *s = map(int, input().split())
        S.append(s)
    P = list(map(int, input().split()))
    ans = 0
    for i in range(1<<N):
        on = []
        for j in range(N):
            if (i >> j) & 1:
                on.append(j+1)
        flag = True
        for m in range(M):
            cnt = 0
            for o in on:
                if o in S[m]:
                    cnt += 1
            if cnt % 2 != P[m]:
                flag = False
                break
            if not flag:
                break
        
        if flag:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

k = []

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))
switches = []
for _ in range(M):
    S = list(map(int, input().split(' ')))
    switches.append(S[1:])

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

ans = 0
def solve(buf):
    global ans

    if len(buf) == N:
        is_solve = True
        for i in range(M):
            n = sum([buf[j-1] for j in switches[i]])
            if (n%2) != P[i]:
                is_solve = False
                break

        if is_solve:
            ans += 1


    else:
        solve(buf + [0])
        solve(buf + [1])

solve([])
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [[] for _ in range(m)]
k = [0 for _ in range(m)]
for i in range(m):
    k[i],*s[i] = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
sw = [0 for _ in range(n)]
for i in range(int(2**n)):
    on = sw[:]
    cnt = 0
    for j in range(n):
        r = i % 2
        i = i // 2
        if r:
            on[j] += 1
    for j in range(m):
        oncnt = 0
        for x in s[j]:
            oncnt += on[x-1]
        if oncnt % 2 == p[j]:
            cnt += 1
    if cnt == m:
        ans += 1
    #print(on,cnt)
print(ans)

Submission status: Accepted

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

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

for i in range(2**N):
    Cou = [0] * M
    for j in range(N):
        if (i >> j) & 1 == 1:
            for k in range(M):
                if (j+1) in Lamp_switch[k]:
                    Cou[k] += 1
                    Cou[k] %= 2

    if Cou == Pon:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
k = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    on = [0]*n
    for j in range(n):
        if ((i>>j)&1):
            on[j] += 1
    flag = 1
    for j in range(m):
        onnum = 0
        for l in range(1,len(k[j])):
            if (on[k[j][l]-1]==1):
                onnum += 1
        if ((onnum%2)!=p[j]):
            flag = 0
    if (flag == 1):
        ans += 1
print(ans)

Submission status: Accepted

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

res=0
for s in range(2 ** n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1,len(k[i])):
            w=k[i][j]
            if s>>(w-1)&1 == 1:#Sをw-1分ビットシフトしたものが1ならば（kで定義された番号のスイッチがONならば）
                cnt +=1
        if cnt %2 !=p[i]:
            judge = False

    if judge:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m = LI()
mx = [list(map(int,input().split())) for i in range(m)]
p = LI()

l = [0]*m
result = 0
for i in range(1 << n):
    flg = True
    for j in range(m):
        count = 0
        for k in range(mx[j][0]):
            if((1 <<(mx[j][k+1]-1)) & i):
                count += 1
        if(count % 2 != p[j]):
            flg = False
            break
    if(flg):
        result += 1

print(result)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
indices = []
for _ in range(M):
    _, *i = map(lambda n: int(n) - 1, input().split())
    indices.append(i)
P = tuple(map(int, input().split()))
print(sum(all(np.array(list(format(n, "0%db" % N)), dtype=np.int8)[indices[m]].sum() & 1 == P[m] for m in range(M)) for n in range(1 << N)))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    switchs = []
    for _ in range(M):
        ks = list(map(int, input().split()))
        switchs.append([1 << s - 1 for s in ks[1:]])
    p = list(map(int, input().split()))
    ans = 0
    for b in range(1 << N):
        f = True
        for i, s in enumerate(switchs):
            c = 0
            for ss in s:
                if b & ss:
                    c += 1
            if c % 2 != p[i]:
                f = False
                break
        if f:
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    switchs = []
    for _ in range(M):
        ks = list(map(int, input().split()))
        switchs.append(ks[1:])
    p = list(map(int, input().split()))
    ans = 0
    for b in range(1 << N):
        f = True
        for i, s in enumerate(switchs):
            c = 0
            for ss in s:
                if b & (1 << (ss - 1)):
                    c += 1
            if c % 2 != p[i]:
                f = False
                break
        if f:
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    line = [int(x) - 1 for x in input().split()]
    k.append(line[0] + 1)
    s.append(line[1:])
p = list(map(int, input().split()))

ans = 0
for combi in range(2**n):
    ok = True
    for index in range(len(p)):
        count = 0
        for i in range(n):
            if(combi >> i) & 1 and i in s[index]:
                count += 1
        if(count % 2 != p[index]):
            ok = False

    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
klis=[]
for i in range(m):
  ababa=list(map(int,input().split()))
  ababa.pop(0)
  klis.append(ababa)
p=list(map(int,input().split()))

res=0
for i in range(0,2**n):
  keep=0
  jyotai=[]
  for j in range(0,n):
    j=n-j-1
    onezero=i//2**j
    jyotai.append(onezero)
    i-=onezero*(2**j)
  for k in range(0,m):
    count=0
    for l in range(0,len(klis[k])):
      if jyotai[klis[k][l]-1]==1:
        count+=1
    if count%2!=p[k]:
      keep=1
      break
  if keep==0:
    res+=1
print(res)

Submission status: Accepted

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

S = [list(map(int, input().split())) for _ in range(M)]
P = [int(i) for i in input().split()]

ans = 0
for i in range(1<<N):
    flg = True
    for j in range(M):
        cnt = 0
        for k in S[j][1:]:
            if ((i >> k-1) & 1):  #1:点灯 0:消灯
                cnt += 1
        if cnt % 2 != P[j]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

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

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

#判定
def jg(A):
    for i in range(M):
        ans=0#点灯しているSWの個数カウント
        for j in range(k[i]):
            ans+=A[s[i][j]]
        if ans % 2 != p[i]:
            return 0
    return 1

dfs([])
print(ok)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = [list(map(int,input().split()))[1:] for i in range(M)]
P = list(map(int,input().split()))
ans = 0
for i in range(0,2 ** N):#0 ~ 3:00 ~ 11
  S = [0] * M
  for j in range(M):
    for k in range(N):
      if (i >> k & 1) and k + 1 in K[j]:
        S[j] += 1
  S = [i % 2 for i in S]
  if S == P:
    ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    flg = True
    for j in range(M):
        c = 0
        for k in S[j][1:]:
            if ((i >> k-1) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                c += 1
        if c % 2 != P[j]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

X = []


def dfs(A):
    if N == len(A):
        X.append(A.copy())
        return
    for i in [0, 1]:
        A.append(i)
        dfs(A)
        A.pop()


dfs([])


def s(m, x):
    s = 0
    for mm in m:
        s += x[mm - 1]
    return s


count = 0
for x in X:
    flg = True  # 一つでも点灯しないものがあったらFalse
    for m, p in zip(S, P):  # 電球ループ
        su = s(m, x)
        if su % 2 != p:
            flg = False
    if flg:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
s = []
for i in range(M):
    dp = [0]*(N)
    tmp = list(map(int,input().split()))
    for j in tmp[1:]:dp[j-1]=1
    s.append(dp)
p = list(map(int,input().split()))
ans = 0

for i in itertools.product([0, 1], repeat=N):
    tmp = 0
    dp = [0]*M
    for I in range(M):
        for j in range(N):
            dp[I] += s[I][j] * i[j]
    for e,i in enumerate(dp):
        dp[e] = i%2
    if dp == p:
        ans+=1
print(ans)

Submission status: Accepted

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

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