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 = map(int,input().split())
data = []
for i in range(m):
    k,*s = map(int,input().split())
    data.append(set(s))
p = list(map(int,input().split()))

ans = 0
for i in range(1<<n):
    on = set()
    for j in range(n):
        if i>>j&1:on.add(j+1)
    if all([len(on&data[l])%2==p[l] for l in range(m)]):ans+=1
print(ans)

Submission status: Accepted

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

case = 0

for i in range(2**N):
    TF=[0]*N
    for j in range(N):
        if ((i>>j)&1):
            TF[N-j-1]=1
    
    #print("\n")
    #print(TF)
    #print("↑今これ")

    c = [0]*m #スイッチ数は最初全部0
    for k in range(m): #k番目の電球に対応するスイッチ数を見ていく

        for l in range(1,len(s[k])): #対応するスイッチ数を合計していく
            c[k] += TF[s[k][l]-1] #cにその合計値を吐く
           
    #print(c)
    for k in range(m):
        if c[k]%2 != p[k]:
            #print("だめ")
            break
    else:
        case += 1
        #print("おｋ")
    
print(case)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def judgeAllBulbsOn(switchOn, conds, p):
    m = len(conds)
    bulbOnFlag = True
    for i in range(m):
        k = conds[i][0]
        numOfSwitchOn = 0
        for j in range(1, k + 1):

            # switchOn is 0 - index
            if switchOn[conds[i][j] - 1] is True:
                numOfSwitchOn += 1
        if numOfSwitchOn % 2 != p[i]:
            bulbOnFlag = False
            break
    return bulbOnFlag


# n:switch, m:bulb
n, m = map(int, input().split())

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

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

switchOn = [False] * n

ans = 0
for bit in range(1 << n):
    for i in range(n):
        if bit & 1 << i:
            switchOn[i] = True
        else:
            switchOn[i] = False
    if judgeAllBulbsOn(switchOn, conds, p):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().strip().split()]
s_ids = []
for i in range(M):
  line = [int(i) - 1 for i in input().strip().split()]
  s_ids.append(line[1:])
p = [int(i) for i in input().strip().split()]

cnt = 0
res = 0
while True:
  cnt2 = cnt
  s = [0] * N
  for i in range(N):
    s[i] = cnt2 % 2
    cnt2 = cnt2 // 2
  are_light = True
  for i in range(M):
    n_on = sum([s[s_id] for s_id in s_ids[i]])
    if n_on % 2 != p[i]:
        are_light = False
  if are_light:
    res += 1
  if cnt == (2 ** N) - 1:
    break
  cnt += 1
print(res)

Submission status: Accepted

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

s=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
for  i in range(1<<(n)):
    for j in range(m):
        c=0
        for ss in s[j][1:]:
            if i&(1<<(ss-1)):
                c+=1
        if c%2!=p[j]:
            break
    else:
        ans+=1

print(ans)

Submission status: Accepted

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

cnt=0
for i in range(2**n):
    # output=[False]*n
    flag=True
    for k in range(len(sl)):
        count=0
        for j in sl[k]:
            if((i>>(j-1))&1):
                count+=1
        if count%2!=p[k]:
            flag=False
            break
    if flag:
        cnt+=1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

cnt=0
for i in range(2**n):
    # output=[False]*n
    flag=True
    for k in range(len(sl)):
        count=0
        for j in sl[k]:
            if((i>>(j-1))&1):
                count+=1
        if count%2!=p[k]:
            flag=False
            break
    if flag:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 2  # type: int


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    M = int(next(tokens))
    S = [[int(next(tokens)) for i in range(int(next(tokens)))] for i in range(M)]
    P = [int(next(tokens)) for i in range(M)]
    Flags = [False for i in range(N)]
    sum = 0
    for i in range(2**N):
        for k in range(N):
            Flags[k] = i & (1<<k) > 0
        fail = False
        for m in range(M):
            c = 0
            for s in S[m]:
                if Flags[s-1]:
                    c+=1
            if c % 2 != P[m]:
                fail = True
                break
        if not fail:
            sum+=1
    print(sum)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# import itertools
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):
    b = list(str(bin(i))[2:].zfill(n))
    # print(b)
    ok = True
    for j in range(m):
        Sum = 0
        for k in range(s[j][0]):
            Sum += int(b[s[j][k+1] - 1])
        # print(i, j, Sum)
        if Sum % 2 != p[j]:
            ok = False
    if ok:
        ans += 1
print(ans)        
# print(s, p)

Submission status: Accepted

Solution code:
N, M = map(int ,input().split())
light = [list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(M)]
p = [int(i) for i in input().split()]

ans = 0

for i in range(1 << N):
    flag = True
    for m in range(M):
        onsum = 0
        for j in range(N):
            if i >> j & 1 and j in light[m]:
                onsum+=1
        if onsum%2!=p[m]:
            flag = False
            break
    if flag == True:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
readline=sys.stdin.readline
def main():
  N,M=map(int,readline().split())
  mlst = [0] * M
  for i in range(1,M+1):
    _, *tmp = map(int,readline().split())
    mlst[i-1] = sum(1<<(i-1) for i in tmp)

  def popcnt(n):
      # 求1的个数
      c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
      c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
      c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
      c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
      c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
      return c


  mod = list(map(int, readline().split()))
  ab = list(zip(mlst, mod))
  res = 0
  for i in range(1<<N):
    for a,b in ab:
      tmp = a & i
      if popcnt(tmp) & 1 != b:
        break
    else:
      res += 1
  print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
readline=sys.stdin.readline
def main():
  N,M=map(int,readline().split())
  mlst = [0] * M
  for i in range(1,M+1):
    _, *tmp = map(int,readline().split())
    for j in tmp:
      mlst[i-1] |= 1<<(j-1)

  def popcnt(n):
      # 求1的个数
      c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
      c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
      c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
      c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
      c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
      return c


  mod = list(map(int, readline().split()))
  ab = list(zip(mlst, mod))
  res = 0
  for i in range(1<<N):
    for a,b in ab:
      tmp = a & i
      if popcnt(tmp) & 1 != b:
        break
    else:
      res += 1
  print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
readline=sys.stdin.readline
N,M=map(int,readline().split())
mlst = [0] * M
for i in range(1,M+1):
  _, *tmp = map(int,readline().split())
  for j in tmp:
    mlst[i-1] |= 1<<(j-1)
    
def popcnt(n):
    # 求1的个数
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c
  
  
mod = list(map(int, readline().split()))
ab = list(zip(mlst, mod))
res = 0
for i in range(1<<N):
  for a,b in ab:
    tmp = a & i
    if popcnt(tmp) & 1 != b:
      break
  else:
    res += 1
print(res)

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

judge=[0]*M
swich=0
count=0

for i in range(2**N):
    swich=str(bin(i)).rjust(N+2,"0")
    judge=[0]*M
    for j in range(M):
        base=0
        for k in ks[j][1:]:
            #print(swich[k+1])
            if swich[k+1]=="1":
                base+=1
        if base%2==1:
            judge[j]=1
    #print(judge)
    if judge==p:
        count+=1

print(count)

Submission status: Accepted

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

b = []
for i in range(2 ** n):
    tmp = [0] * (n)
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    b.append(tmp)
    
ans = 0
for i in range(2 ** n):
    bc = b[i]
    flag = True
    for j in range(m):
        t = 0
        for onsw in s[j]:
            t += bc[onsw - 1]
        if t%2 != p[j]:
            flag = False
    if flag:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lights=[list(map(lambda x: int(x)-1, input().split()))[1:] for i in range(M)]
p=list(map(int,input().split()))
ans=0

for i in range(1<<N):
  for m in range(M):
    on_sum=0
    for j in range(N):
      if i>>j &1 and j in lights[m]:
        on_sum+=1
    if on_sum%2!=p[m]:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  s=[list(map(int,input().split()))[1:] for _ in [0]*m]
  p=list(map(int,input().split()))
  count=0
  for i in range(pow(2,n)):
    x=0
    for j in range(m):
      if sum(i&(1<<(k-1))> 0 for k in s[j]) % 2 == p[j]:
        x+=1
    if x==m:
      count+=1
  print(count)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = []
for _ in range(M):
    inp = [int(x) for x in input().split()][1:]
    lst_ = [0] * N
    for i in inp:
        lst_[i - 1] = 1
    s.append(lst_)


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

for i in range(2 ** N):
    lst = [0]*M
    for j in range(N):
        if i & 1:
            for k in range(M):
                lst[k] += s[k][j]
        i >>= 1
    flag = 1
    for j in range(M):
        flag *= 1 - (lst[j] & 1)^ p[j]
    if flag:
        count += 1

print(count)

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

ans = 0
for i in range(2**n):
    state = bin(i)[2:]
    state = '0'*(n - len(state)) + state
    state = [int(i) for i in state]
    flag=1
    for j in range(m):
        sum_k = 0
        for k in S[j]:
            sum_k += state[k-1]
        if sum_k %2 != P[j]:
            flag = 0
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

for bit in range(1 << n):
    for i in range(m):
        flag = True
        acc = 0
        for s in k[i][1:]:
            #スイッチssが点灯しているかどうか
            if (bit & (1 << s)):
                acc += 1
        if acc % 2 != p[i]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
for _ in range(m):
    _, *args = map(int, input().split())
    s.append(args)
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    for j in range(m):
        sw = 0
        for k in range(n):
            if (i >> k) & 1 and k + 1 in s[j]:
                sw += 1
        if sw % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    f = True
    for k in range(m):
        cnt = 0
        for j in range(n):
            if ((i >> j) & 1 and j+1 in ss[k]):
                cnt += 1
        if cnt % 2 != p[k]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#128_C
n,m=map(int,input().split())
sw=[]
for _ in range(m):
    k,*s=map(int,input().split())
    sw.append(s)
p=list(map(int,input().split()))

ans=0
for i in range(2**n):
    L=[(i>>j)&1 for j in range(n)]
    if all([sum([L[s-1] for s in sw[k]])%2==p[k] for k in range(m)]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
K = [list(map(int1, readline().split())) for _ in range(M)]
P = list(map(int, readline().split()))

ans = 0
for bit in range(1 << N):
    for i in range(M):
        flag = True
        acc = 0
        for s in K[i][1:]:
            if (bit & (1 << s)):
                acc += 1
        if acc % 2 != P[i]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switch_state = [None] * N
which_switch = []

for i in range(M):
    which_switch.append(list(map(int, input().split())))
    del(which_switch[i][0])

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

cnt = 0
for i in range(1<<N):
    flag = 0
    for j in range(M):
        check = 0
        for el in which_switch[j]:
            check += (1<<(el-1))
        if str(bin(i & check)).count('1') % 2 != p[j]:
            flag = 1
            break
    if flag == 1:
      continue
    cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int,input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))
    # print(s)

    # スイッチONOFFパターンをbit全探索
    ans = 0
    for i in range(0, 2**N):

        # ONOFFリスト取得
        switchs = [False for _ in range(N)]
        for j in range(N):
            if (i>>j) & 1:
                switchs[j] = True
        # print(bin(i))
        # print(switchs)

        # 各電球が点灯しているか判定
        ok = True
        for si,pi in zip(s,p):
            # print(si)
            # print(pi)
            # ONの個数
            on_count = [switchs[sij-1] for sij in si].count(True)
            # print(on_count)
            # 消灯していた場合
            if on_count % 2 != pi:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


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

    ans = 0

    for i in range(2 ** n):

        flag = False
        if flag == False:
            light = 0
            for a in range(m):
                tmp = p[a]
                count = 0
                for j in s[a]:
                    if (i >> (j - 1)) & 1:
                        count += 1
                if count % 2 != tmp:
                    flag = True
                    break

                light += 1


        if light == m:
            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 _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for state in range(2**n):
    ons = [0] * m
    for i in range(m):
        for j in ks[i][1:]:
            if( (state >> (j-1)) & 1  ) == 1:
                ons[i] += 1

    light = 0
    for i in range(m):
        if( p[i] == (ons[i] % 2) ):
            light += 1

    if(light == m):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
k = [None] * M
s = [None] * M
for i in range(M):
  k[i], *s[i] = map(int, input().split())

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

ans = 0
for i in range(2**N):
  tmp = 0
  for j in range(M):
    count = 0
    for l in range(k[j]):
      if (i >> (s[j][l]-1)) & 1:
        count += 1
    if count % 2 == p[j]:
      tmp += 1
  if tmp == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = list(map(int, input().split(" ")))

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


points = list(map(int, input().split(" ")))
# スイッチの数はN個。このkonおスイッチにon/offの状態があるので2^N
# これの全部の組み合わせを出して、条件を全て満たせる組み合わせがあればクリア
count = 0
for i in range(2**N):
    for j, switch in enumerate(switches):
        n = 0
        for k in switch:
            # print(i, k, i >> (k - 1))
            n += i >> (k - 1)
        # print("========")
        if n % 2 == points[j]:
            continue
        else:
            break
    # breakによって抜けなかった時
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
N, M = list(map(int, input().split(" ")))

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


points = list(map(int, input().split(" ")))
# スイッチの数はN個。このkonおスイッチにon/offの状態があるので2^N
# これの全部の組み合わせを出して、条件を全て満たせる組み合わせがあればクリア
count = 0
for i in range(2**N):
    for j, switch in enumerate(switches):
        n = 0
        for k in switch:
            n += i >> (k - 1) & 1
        if n % 2 == points[j]:
            continue
        else:
            break
    # breakによって抜けなかった時
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import product

n, m = [int(i) for i in input().split()]
k = []
s = []
for _ in range(m):
    s.append([int(i) for i in input().split()])
    k.append(s[-1].pop(0))
p = [int(i) for i in input().split()]

cnt = 0
for switches in product(range(2), repeat=n):
    num_of_on_switches = [0] * m
    for i, switch in enumerate(switches):
        if switch:
            for k, ss in enumerate(s):
                if i+1 in ss:
                    num_of_on_switches[k] += 1

    for i, pp in enumerate(p):
        if num_of_on_switches[i] % 2 != pp:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
q=[]
for i in range(m):
    s=list(map(int,input().split()))
    res=0
    for i in range(s[0]):
        res+=2**(s[i+1]-1)
    q.append(res)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    cnt=0
    for j in range(m):
        cnt0=0
        for k in range(n):
            if ((q[j]&i)>>k)&1==1:
                cnt0+=1
        if cnt0%2==p[j]:
            cnt+=1
        else:
            break
    if cnt==m:
        ans+=1
print(ans)

Submission status: Accepted

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

# print("n,m:",n,m)
# print("s:",s)
# print("p:",p)

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

# print("---start---")
ans = 0
for i in range(2**n):
    bitnow = bitlist(i,n)
    # print("bitnow:",bitnow)
    flag = 0
    for j in range(m):
        checker = 0
        for l in s[j]:
            if bitnow[l]==1:
                # print("l:",l)
                checker += 1
        # print("checker:",checker)
        # print("p[j]:",p[j])
        if checker%2 != p[j]:
            flag = 1
    if flag == 0:
        ans += 1
    # print("ans:",ans)
    # print("--------------")

print(ans)

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):
    s=[0]*n
    f=1
    for j in range(n):
        if (i>>j)&1:
            s[j]=1
    for j in range(m):
        c=0
        for k in range(1,1+l[j][0]):
            if s[l[j][k]-1]:
                c+=1
        if c%2!=p[j]:
            f=0
            break
    if f:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
sw = [[0] * N for _ in range(M)]
for i in range(M):
    ks = input().split()
    for j in ks[1:]:
        sw[i][int(j)-1] = 1
P = list(map(int, input().split()))

ans = 0
for switch in product(range(2), repeat=N):
    isOK = True

    for i in range(M):
        cnt = 0
        for j in range(N):
            if sw[i][j] == switch[j] == 1:
                cnt += 1
        if cnt % 2 != P[i] % 2:
            isOK = False
            break

    if isOK:
        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(1 << n):
    sw = set()
    count = 0
    for j in range(n):
        if ((i >> j) & 1):
            sw.add(j+1)
    for k,si in enumerate(s):
        num_on = len(sw & set(si[1:]))
        if num_on % 2 ==  p[k]:
            count += 1
    if count == 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)]
K = [s[0] for s in S]
S = [s[1:] for s in S]
P = list(map(int,input().split()))

from itertools import product
ans = 0
for d in product([0,1],repeat=n):  
  count = 0
  for mi in range(m):
    on = sum([d[S[mi][si]-1]==1 for si in range(K[mi])])    
    if on % 2 == P[mi]:
      count += 1        
  if count == m:
    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()))
ans = 0
for bit in range(1 << N):
    for m in range(M):
        if sum([bit & (1 << (s-1)) > 0 for s in S[m]]) % 2 != P[m]:
            break
    else:
        ans += 1
print(ans)

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

x=2**N
ans=0
for i in range(x):
    A=list(format(i,'b').zfill(N))
    flag=1
    for j in range(M):
        buf=0
        for k in range(Ks[j][0]):
            buf+=int(A[Ks[j][k+1]-1])
        if buf%2!=P[j]:
            flag=0
            break
    ans+=flag
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
light = [list(map(lambda x: int(x)-1, input().split()))[1::] for _ in range(m)]
p = list(map(int, input().split()))
for i in range(m):
    light[i].insert(0, p[i])

#print(light)

ans = 0
for i in range(2**n):
    pattern = ''
    for j in range(n):
        if (i >> j) & 1:
            pattern += '1'
        else:
            pattern += '0'
    # print(pattern)
    flag = True
    for k in range(m):
        counter = 0
        for switch in light[k][1::]:
            counter += int(pattern[switch])
        if counter % 2 != light[k][0]:
            flag = False
            break
    if flag: ans += 1

print(ans)

Submission status: Accepted

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

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

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

ans = 0
for i in range(2 ** n):
    for index, light in enumerate(lights):
        n = 0
        for j in light:
            n += i >> (j - 1) & 1
        if n % 2 == p[index]:
            continue
        else:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt=0
for i in range(2**n):
    Q=0
    switch=set([i+1 for i,j in enumerate(format(i,"b").zfill(n)[::-1]) if j == '1'])
    for k,j in enumerate(S):
        if len(switch&set(j))%2==P[k]:
            Q+=1
    if Q==m:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
L = []
for i in range(m):
    L.append(list(map(int,input().split()))[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    #tmp=np.array([i>>s&1 for s in range(n)])
    #if q==[sum(tmp[array(i)-1])%2for i in L]:
    #    ans+=1
    flag = True   
    a = format(i,"b").zfill(n)#[::-1]
    for j in range(m):
        sw = 0
        for k in range(len(L[j])):
            if a[L[j][k] -1] == "1":
                sw +=1
        if sw%2 != p[j]:
            flag = False
            break
    if flag:
        ans +=1
print(ans)