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())
#ks[i][0]がk_i
ks = [[int(i) for i in input().split()]for i in range(M)]
p=list(map(int,input().split()))
ans=0
for i in range(2**N):
    flag=0
    #Onoff[i]=0はスイッチiのOFFを、=1はONを表す
    OnOff = [0]*N
    for j in range(N):
        if (i>>j) & 1:
            OnOff[j]=1
    
    for j in range(M):
        count=0
        for l in range(1,len(ks[j])):
            if(OnOff[ks[j][l]-1]==1):
                count+=1
        if(p[j]==0 and count%2==0):
            flag+=1
        elif(p[j]==1 and count%2==1):
            flag+=1
        else:
            pass
    
    if(flag==len(p)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = []
for _ in range(m):
    k, *s = map(lambda x: int(x)-1, input().split())
    S.append(s)
P = list(map(int, input().split()))

bit = []
ans = 0


def dfs(cnt):
    if cnt == n:
        for j in range(m):
            if P[j] != sum(bit[idx] for idx in S[j]) % 2:
                break
        else:
            global ans
            ans += 1
    else:
        bit.append(0)
        dfs(cnt+1)
        bit.pop()

        bit.append(1)
        dfs(cnt+1)
        bit.pop()


dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int, input().split())
S = []
for _ in range(m):
    k, *s = map(lambda x: int(x)-1, input().split())
    S.append(s)
P = list(map(int, input().split()))
ans = 0
for bit in product((0, 1), repeat=n):
    for j in range(m):
        switch_cnt = sum(bit[idx] for idx in S[j])
        if P[j] != switch_cnt % 2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
datas = []
for i in range(M):
  data=list(map(int, input().split()))
  datas.append(data[1:])
p = list(map(int, input().split()))

result = 0
for sw in range(2**N):
  lights = True
  for i,data in enumerate(datas):
    count = 0
    for d in data:
      if sw >> (d-1) & 1 == 1:
        count += 1
        
    if count % 2 != p[i]:
      lights = False

  if lights:
    result += 1
print(result)

Submission status: Accepted

Solution code:
def solve(L):
    for i in range(m):
        cnt = 0
        for j in range(1, s[i][0]+1):
            if L[s[i][j] - 1] == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            return 0
    else:
        return 1

n, m = map(int, input().split())
*s, p = [list(map(int, input().split())) for _ in range(m+1)]
ans = 0
for i in range(2 ** n):
    L = [0] * n
    for j in range(n):
        if ((i >> j) & 1) == 1:
            L[j] = 1
    ans += solve(L)
print(ans)

Submission status: Accepted

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

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

#print(list1)
list2 = []

## bit全探索 
#list1 = ['A', 'B', 'C']
for i in range(list1[1]):
    list2.append(list(map(int,input().split())))

list3 = list(map(int,input().split()))
#print(list2)
#print(list3)
a = 0
# 全探索
for i in range(2**list1[0]):  # 空集合を除く場合はrange(1, 2**len(list1))
    for k in range(list1[1]):
        t = 0
        for j in range(list1[0]):
#            print(i,k,j,i >> j)
            if j+1 in list2[k][1:] and (i >> j) &1 == 1:
#                print(i,k,j)
                t += 1
#        print(t)
        if t%2 != list3[k]:
#            print("break",i,k,j)
            break
    else:
#        print(i)
        a += 1 
print(a)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [0]*M
for i in range(M):
  A, *B= map(int, input().split())
  X[i] = B
p = list(map(int, input().split()))
onoff =[0]*M
count = 0
for i in range(2**N):
    for j in range(N):
        if (i>>j) & 1:
            for k in range(M):
                if j+1 in X[k]:
                    onoff[k] += 1
    flag = 1
    for i in range(M):
        if onoff[i] % 2 != p[i]:
            flag = 0
    if flag:
        count += 1
    onoff = [0]*M
print(count)

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()))
  del s[i][0]
p=list(map(int,input().split()))
count=0
for i in range(2**n):
  for k in range(m):
    temp=0
    for j in range(n):
      if ((i >> j) & 1) and j+1 in s[k]:
        temp=temp+1
    if temp%2!=p[k]:
      break
  else:
    count=count+1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = [0] * M
for i in range(M):
  K[i] = list(map(int, input().split()))
  K[i].pop(0)
#print(K)

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

ans = 0
for i in range(2 ** N):#最大1000
  now = [0] * (N + 1)
  x = 1
  for j in range(N):#最大10
    if ((i >> j) & 1):
      now[j + 1] = 1
  for k in range(M):# 10 * 10
    now2 = 0
    for a in K[k]:
      if now[a] == 1:
        now2 += 1
    if now2 % 2 != p[k]:
      x = 0
  ans += x
  
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    l = list(map(int,input().split()))
    k.append(l[0])
    s.append(l[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    l = []
    for j in range(n):
        l.append(i>>j&1)
    cnt = 0
    for j in range(m):
        c = 0
        for h in s[j]:
            c += l[h-1]
        if c%2 == p[j]:
            cnt += 1
    if cnt == m:
        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 = input().split()

ans = 0
flag = 0
for x in range(1 << n):
    for i in range(m):
        k = ks[i][0]
        s = ks[i][1:]
        c = 0
        for j in range(k):
            if 1 & (x >> s[j]-1):
                c += 1
        if c%2 != int(p[i]):
            flag = 1
            break
    if flag == 0:
        ans += 1
    flag = 0
 
print(ans)

Submission status: Accepted

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

ans = 0
for pattern in range(1 << N):
    for i in range(M):
        k = switches[i][0]
        switch = switches[i][1:]
        count= 0
        for j in range(k):
            if 1 & (pattern >> switch[j]-1):
                count += 1
        
        if count % 2 != P[i]:
            break
    else: ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

n,m = map(int,input().split())
S = []
k = []
for i in range(m):
    s = input().split()
    k.append(int(s[0]))
    d = []
    for j in range(1,len(s)):
        d.append(int(s[j]))
    S.append(d)
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    li = [False]*n
    flag = 0
    for j in range(n):
        if (i>>j)&1:
            li[n-j-1] = True
    for j in range(m):
        cnt = 0
        for l in range(k[j]):
            if li[S[j][l]-1]:
                cnt += 1
        if cnt%2 == p[j]:
            flag = 1
        else:
            flag = 0
            break
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M = map(int, readline().split())
S = [[] for _ in range(M)]
for i in range(M):
    _, *S[i] = [int(s) - 1 for s in readline().split()]
P = list(map(int, readline().split()))

ans = 0
for r in range(N + 1):
    for comb in combinations(range(N), r):
        switches = [False] * N
        for i in comb:
            switches[i] = True

        all_lit = True
        for j in range(M):
            if sum(switches[k] for k in S[j]) % 2 != P[j]:
                all_lit = False
                break

        if all_lit:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
judge = tuple(map(int, input().split()))
count =0
switch = list(itertools.product([0,1], repeat=n)) #nがtupleの要素数
for i in range (len(switch)):
    #スイッチ全探索
    for j in range(m):
        cnt = 0
        #各電球に焦点
        for k in range(l[j][0]):
            #電球のスイッチ条件に焦点
            cnt += switch[i][l[j][k+1]-1]
        if cnt % 2 != judge[j]:
            break
        else:
            if j == m-1:
                count += 1
print(count)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M = map(int, readline().split())
S = [[] for _ in range(M)]
for i in range(M):
    _, *S[i] = [int(s) - 1 for s in readline().split()]
P = list(map(int, readline().split()))

ans = 0
for i in range(1 << N):
    switches = [bool(i & (1 << j)) for j in range(N)]
    all_lit = True
    for j in range(M):
        if sum(switches[k] for k in S[j]) % 2 != P[j]:
            all_lit = False
            break
    if all_lit:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

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

d = defaultdict(set)
res = 0

for key in range(1, M+1): # keyは電球を指定
    l = list(map(int, input().split()))
    l.pop(0)
    for i in l:
        d[key].add(i)  # dict = {(電球番号(key): [スイッチ番号(i), ...],...}

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

for a in product(*((0, x) for x in range(1, N+1))):
    light = 0 # 光っている電球の個数
    for key in range(1, M+1):
        count = len(d[key] & set(a)) # 電球番号(key)のスイッチがONになっている個数
        if count%2 == p[key-1]:
            light += 1
    if light == M:
        res += 1

print(res)

Submission status: Accepted

Solution code:

import numpy as np

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

#データの入力
array = np.array([[0]*N]*M)
for i in range(M):
    switch = list(map(int, input().split()))
    List = [0]*N
    for j in switch[1:]:
        List[j-1] = 1
    array[i] = np.array(List)



condition = np.array([list(map(int, input().split()))])


def onoff(array, List):
    return np.dot(array, List) % 2

def mklist(i):
    binnum = bin(i)
    binnum = binnum[2:].zfill(N)
    return np.array([list(map(int, list(binnum)))]).T

ans = 0
for i in range(2**N):
    if np.all(condition == onoff(array, mklist(i)).T):
        ans = ans + 1
    
print(ans)

Submission status: Accepted

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

    for i in range(2**N):
        flag = False
        denki = []
        for j in range(N):

            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                denki.append(j+1)  # フラグが立っていたら num に数字を詰める
        for k in range(M):
            KS = ks[k]
            idk = KS[0]
            kosuu = 0
            for l in range(1, idk+1):
                if KS[l] in denki:
                    kosuu += 1
            if kosuu % 2 != p[k]:
                flag = False
                break
            else:
                flag = True
        if flag:
            comb += 1

    print(comb)


if __name__ == '__main__':
    main()

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)):
    count = 0
    for j in range(M):
        k = ks[j][0]
        on = 0
        for s in ks[j][1:]:
            if i & (1 << (s-1)):
                on += 1
        
        if on % 2 == p[j]:
            count += 1

    if count == M:
        ans += 1

print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    s = [list(map(int, input().split()[1:])) for _ in range(m)]
    s_maps = [[0] * n for _ in range(m)]
    p = list(map(int, input().split()))
    for i in range(m):
        for j in s[i]:
            s_maps[i][j-1] = 1

    ans = 0
    for i in range(2**n):
        switch_str = format(i, '0{}b'.format(n))
        switch_state = list(map(int, list(switch_str)))
        flag = True
        for j, s_map in enumerate(s_maps):
            s_on = [i * j for i, j in zip(s_map, switch_state)]
            if sum(s_on) % 2 != p[j]:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=2**n
for i in range(2**n):
    for ind,light in enumerate(s):
        SwitchOn=0
        for ConnectedSwitch in light:
            if(i >> (ConnectedSwitch - 1) & 1):
                SwitchOn += 1
        if(SwitchOn % 2 != p[ind]):#ライトがoffなら
            ans-=1
            break
print(ans)

Submission status: Accepted

Solution code:
#C
n, m = map(int, input().split())
l = []
ans = 0
for i in range(m):
    l.append(list(map(int, input().split())))
for i in range(m):
    del l[i][0]
p = list(map(int, input().split()))
for i in range(2**n):
    for j in range(m):
        cnt_on = 0 
        for num in range(n):
            if ((i >> num) & 1) and (n-num in l[j]):
                cnt_on += 1
        if cnt_on % 2 != p[j]:
            break
    else:
        ans += 1        
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ans=0
ALL=[]
for i in range(M+1):
  a=list(map(int,input().split()))
  ALL+=[a]
ans=0  
for i in range(2**N):
  switch=[0 for _ in range(N)]
  for k in range(N):
    if (i>>k)&1:
      switch[k]=1
  for t in range(M):
    check=0
    for p in range(1,ALL[t][0]+1):
      if switch[ALL[t][p]-1]==1:
        check+=1
    if check%2!=ALL[-1][t]:
      break
    elif t==M-1:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split()))[1:] for _ in range(M)]
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
  lit=[0]*M
  for j,switches in enumerate(L):
    cnt=0
    for s in switches:
      if i>>(s-1)&1:cnt+=1
    if cnt%2==P[j]:lit[j]=1
  if all(lit):ans+=1 
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
data = ILL(M)
p = IL()

B = []
for d in data:
  d = d[1:]
  b = 0
  for i in d:
    b += 1<<(i-1)
  B.append(b)
  
ans = 0
for k in range(1<<N):
  flag = 1
  for i in range(M):
    b = B[i]
    if count_bit(b&k) % 2 != p[i]:
      flag *= 0
  if flag:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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 i in range(2**n):
    ol=[0]*n
    cntt=0
    for j in range(n):
        if ((i>>j)&1):
            ol[j]=1
    #print(ol)
    for k in range(m):
        cnt=0
        for j in range(ks[k][0]):
            if ol[ks[k][j+1]-1]==1:
                cnt+=1
        
        if cnt%2==p[k]:
            cntt+=1
            #print(ks[k],p[k],cnt)
    if cntt==m:
        ans+=1
        #print(ol)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, M = [int(i) for i in input().split()]
    kk, ss = [], []
    for _ in range(M):
        k, *s = [int(i) for i in input().split()]
        kk.append(k)
        ss.append(s)
    p = [int(i) for i in input().split()]
    ans = 0
    for i in range(2**N):
        lights = [0] * M
        for j in range(M):
            count = 0
            for sw in ss[j]:
                if (i >> (sw - 1)) & 1:
                    count += 1
            if count % 2 == p[j]:
                lights[j] = 1
        if 0 not in lights:
            ans += 1
    print(ans)


resolve()

Submission status: Accepted

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

#print(ks[0][1:])
ans = 0
for i in range(2**n):
  count = [0]*m
  flg = True
  for j in range(n):  
        if ((i >> j) & 1):  
          for k in range(m):
            if j+1 in ks[k][1:]:
              count[k] += 1
  
  #print("i:" + str(i))
  #print(count)
  for l in range(m):
    if count[l] % 2 != p[l]:
      flg = False
      break
  if flg:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lights = []
for i in range(1,M+1):
  light = list(map(int, input().split()))
  lights.append(light)

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

ans = 0
for i in range(2**N):
  all = True
  for j in range(M):
    ons = 0
    for s in lights[j][1:]:
      if (i>>(s-1) & 1):
        ons += 1
    if ons % 2 != ps[j]:
      all = False
      break            
  if all:
    ans += 1

print(ans)

Submission status: Accepted

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

l = []
for i in range(2**len(li)):
    x = [0]*n
    for j in range(len(li)):
        if i >> j & 1:
            x[j] = 1
    l.append(x)

s = []
for i in range(m):
  a = [int(i)-1 for i in input().split()]
  s.append(a[1:])
  
p = [int(i) for i in input().split()]

ans = 0
for i in l:
  b = 0
  for j in range(len(s)):
    a = 0
    for k in range(len(s[j])):
      if i[s[j][k]] == 1:
        a += 1
    if a%2 == p[j]:
      b += 1
  if m == b:
    ans += 1
    
print(ans)

Submission status: Accepted

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

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

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

ans = 0

for i in range(2**N):
  switch_states = [(i >> j) & 1 for j in range(N)]
  
  for di, d in enumerate(ds):
    count = 0
    
    for s in d:
      count += switch_states[s-1]
      
    if count % 2 != P[di]:
      ans -= 1
      break

  ans += 1
        
        
print(ans)

Submission status: Accepted

Solution code:
def solve():
    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, 2**(N+1)):
        bi = bin(i)[3:]
        t = [0] * (M*1)
        for i, si in enumerate(s):
            for j, b in enumerate(list(bi)):
                if b == '1' and j+1 in si:
                    t[i] += 1
            if t[i] % 2 != p[i]:
                ans -= 1
                break
        ans += 1
    
    return ans
  
print(solve())

Submission status: Accepted

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

form ="0"+str(n)+"b"
ans = 0
for i in range(2**n):
    ptn = format(i,form)
    light = True
    for j in range(m):
        s = sum(int(ptn[k-1])for k in l[j])
        if s%2 !=p[j]:
            light = False
    if light == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
ks = [list(map(int, sys.stdin.readline().split())) for i in range(M)]
k = [i[0] for i in ks]
s = [i[1:] for i in ks]

p = list(map(int, sys.stdin.readline().split()))
ans = 0

for i in range(2 ** N):
    op = [1] * N
    for j in range(N):
        if (i >> j) & 1:
            op[j] = 0
    T = [False] * M
    for h in range(M):
        c = 0
        for l in s[h]:
            if op[l - 1]:
                c += 1
        if p[h] == c % 2:
            T[h] = True
    if all(T):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = list(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(2**n):
    # 1,2,3...,Nのスイッチの状態
    state=[(i>>j)&1 for j in range(n)]
#    print('state=',state)
    ok=1
    for ii, x in enumerate(k):
#        print('x=',x)
        on_cnt=0
        for y in x:
            if state[y-1]==1:
                on_cnt+=1
        if on_cnt%2!=p[ii]:
            ok=0
            break
    if ok==1:
        ans+=1

print(ans)

Submission status: Accepted

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


def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

ans=0

for bit in range(2**n):
    ok=True
    for mm in range(m):
        on=0
        for i in s[mm]:
            if bit & 2**(i-1)!=0:
                on+=1
        if on%2==p[mm]:
            pass
        else:
            ok=False

    if ok:ans+=1
print(ans)

Submission status: Accepted

Solution code:
SN,LN=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(LN)]
p=list(map(int,input().split()))

c=0
for i in range(1<<SN):
  tmp=[0]*SN
  judge=True
  for j in range(SN):
    if (i>>j)&1==1:
      #tmpにon/offの情報を0/1で入れる
      tmp[j]=1
      
  for k in range(LN):
    sum=0
    #ある電球のスイッチの番号を取得
    for x in S[k][1:]:
      # その番号のスイッチがonか否かを判定
      if tmp[x-1]==1:
        #onの個数を記録
        sum+=1
    #k番目の電球がonでなければその時点でfalse
    if sum%2!=p[k]:
      judge=False
  #あるtmpの状態で全ての電球がonならcにカウント
  if judge:
    c+=1

print(c)

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
s = [list(map(int,input().split()))[1:] for i in range(m)]
#print(s)
p = list(map(int,input().split()))
ans = 0
for i in itertools.product(range(2),repeat=n):
    c = 0
    st = 0
    for j in s:
        t = p[st]
        st += 1
        for k in j:
            t += i[k-1]
        if t%2 == 0:
            c += 1
    if c == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    KS = [il() for _ in range(M)]
    P = il()

    ret = 0
    for n in range(1 << N):
        l = [False]*M
        for m in range(len(KS)):
            K, *S = KS[m]
            on = 0
            for s in S:
                if n >> (s-1) & 1:
                    on += 1
            if on % 2 == P[m]:
                l[m] = True
        if all(l):
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ds = []
for _ in range(M):
    ds.append(tuple(map(int, input().split()))[1::])
    
P = tuple(map(int, input().split()))

# スイッチのon/offについて全探索
oks = 0
for i in range(2**N):
    switch_states = [(i>>j)&1 for j in range(N)]
    # すべての電球について
    for di, d in enumerate(ds):
        # 関連するスイッチがonの個数を数える
        switch_counts = 0
        for s in d:
            switch_counts += switch_states[s-1]
        if switch_counts%2 != P[di]:
            break
    else:
        oks += 1
print(oks)

Submission status: Accepted

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

m = [0] * M # 電球のonoffチェック。on:1 off:0
cnt1 = 0 # 1の個数を数える
cnt2 = 0 # 答え

for i in range(2 ** N):
  for j in range(M):
    for k in range(l[j][0]):
      if (i >> (l[j][k+1] - 1) & 1):
        cnt1 += 1
    if cnt1 % 2 == p[j]:
      m[j] = 1
    cnt1 = 0
  if m == [1] * M:
    cnt2 += 1
  m = [0] * M
print(cnt2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,m = imap()
k,s = [],[]
for i in range(m):
    tmp = iarr()
    k.append(tmp[0])
    s.append([num-1 for num in tmp[1:]])
p = iarr()

ans = 0
for i in range(2**n):
    bin = iarr(n)
    for j in range(n):
        if i>>j&1: bin[j] = 1
    flag = 1
    for ii,ss in enumerate(s):
        cnt = 0
        for num in ss: cnt += bin[num]
        if cnt%2 == p[ii]: continue
        else: flag = 0; break
    if flag: ans += 1
print(ans)