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:
#!/usr/bin/env python
# coding: utf-8

# In[12]:


import sys
#import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
#import numpy as np


# In[15]:


cnt = 0
#print(itertools.product(range(0, 2), repeat=N))
for on in itertools.product(range(0, 2), repeat=N):
    for i in range(M):
        sum_ = 0
        for j in range(l[i][0]):
            ind = l[i][j+1]-1
            sum_ += on[ind]
        if sum_%2 != l[-1][i]:
            break
    else:
        cnt += 1
print(cnt)

"""
s = range(N)
cnt = 0
# N個がonになる
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))# N個onになる通り
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(l[i][0]):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
#0個on
o = list(range(N))
a = np.zeros((N))
for i in range(M):
    sum_ = 0
    for j in range(l[i][0]):
        ind = l[i][j+1]-1
        sum_ += a[ind]
    o[i] = sum_%2==l[-1][i]
if np.all(o):
    cnt += 1
print(cnt)
"""


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S_lists = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for n in range(2**N):
  l = 1
  for p, S in zip(P, S_lists):
    l *= (sum([int(bin(n)[2:].zfill(N)[s-1]) for s in S]) % 2 == p)
  count += l
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[[0 for h in range(n)] for i in range(2**n)]
b1=[[0 for i in range(m)] for h in range(2**n)]
#0~2**n-1を2進数表記し、リストaに記録する(各位の10はスイッチのonoffに対応)
for i in range(2**n):
  b=i
  for j in range(n):
    c=b//(2**(n-j-1))
    a[i][j]+=c
    b-=c*(2**(n-j-1))
#それぞれの数について、電球が点灯するかどうかを検証する（各位が電球の点灯する条件を満たしているか）
for i in range(m):
  lights=list(map(int,input().split()))
  for j in range(2**n):
    for h in range(len(lights)-1):
      b1[j][i]+=a[j][lights[h+1]-1]
check=list(map(int,input().split()))
#検証パート
ans=0
for i in range(2**n):
  flag=0
  for j in range(m):
    if b1[i][j]%2 != check[j]:
      flag=1
      break
  if flag==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
sw = []
ki = []
counter = 0
for i in range(m):
    inp = list(map(int, input().split()))
    sw.append(inp[1:])
    ki.append(inp[0])
criterion = list(map(int, input().split()))
for switch in range(2**n):
    flash = defaultdict(int)     #flash+criterion%2 = 0なら発光
    for j in range(n):
        if ((switch >> j) & 1):
            for light in range(m):  
                if (j + 1) in sw[light]:
                    flash[light] += 1
    token = True
    for l in range(m):
        if (flash[l] + criterion[l]) % 2 == 1:
            token = False
    if token:
        counter+= 1
print(counter)

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

pat = [ format(i, '0'+ str(N) + 'b') for i in range(pow(2, N))]
count = 0

for p in pat:
#     print('--- '+p)
    breaked = False
    for i in range(M):
        cnt = 0
#         print('== ' + str(i))
        for s in Ks[i][1:]:
#             print(s, p[s-1])
            if p[s-1] == '1':
                cnt += 1
#         if cnt == 0 or cnt % 2 != P[i]:
        if cnt % 2 != P[i]:
            breaked = True
#             print('break', cnt, P[i])
            break
    if not breaked:
        count += 1

        
print(count)

Submission status: Accepted

Solution code:
def add(s,d):
     sum=0
     for i in d[1:]:
          sum+=s[i] 
     return sum

def check(m):
    for i in range(m):
        if add(s, d[i]) % 2 == p[i]:
            pass
        else :
            return -1
    return 1
        
        
d = []
s=[]
inc=0

n, m = (int(x) for x in input().split())
for i in range(m):
    i = [int(i) for i in input().split()] 
    d.append(i)
p = [int(i) for i in input().split()]

r = 2 ** n

for i in range(r):
    x = str(bin(i).split('b')[1]).zfill(n + 1)
    s=list(x)
    s= [int(s) for s in s]
    if check(m) == 1:
            inc +=1
    
print(inc)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    flag = 0
    b = bin(i)[2:]
    b = '0' * (N-len(b)) + b
    for j in range(M):
        tmp = 0
        switches = S[j]
        for k, v in enumerate(switches):
            if b[v-1] == '1':
                tmp += 1
        if tmp % 2 != P[j]:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
ss = product([0, 1], repeat=n)
lb = [[0] * n for _ in range(m)]
for i in range(m):
    tmp = list(map(int, input().split()))
    k = tmp.pop(0)
    for j in tmp:
        lb[i][j-1] = 1

p = list(map(int, input().split()))
ans = 0
for state in ss:
    flag = True
    sc = 0
    for j, l in enumerate(lb):
        if sum([min(e) for e in zip(l, state)]) % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
ss = product([0, 1], repeat=n)
lb = [[0] * n for _ in range(m)]
for i in range(m):
    tmp = list(map(int, input().split()))
    k = tmp.pop(0)
    for j in tmp:
        lb[i][j-1] = 1

p = list(map(int, input().split()))
ans = 0
# n個スイッチのパターンループ
for state in ss:
    flag = True
    sc = 0
    # 電球のスイッチ条件1～iループ
    for j, l in enumerate(lb):
        if sum([min(e) for e in zip(l, state)]) % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (1 << (sw - 1)) & bits:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)

Submission status: Accepted

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)

Submission status: Accepted

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
            # if (1 << (sw - 1)) & bits: # こちらの判定でも良い
                cnt += 1
        if cnt%2 != lst_p[i]:
            judge = False
    if judge:
        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

s = [0] * n
for i in range(2 ** n):
    temp = i
    for j in range(n):
        s[j] = temp % 2
        temp //= 2
    for j in range(m):
        z = 0
        #print(k[j])
        for x in range(1, k[j][0]+1):
            z += s[k[j][x] - 1]
        if p[j] != z % 2:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
kls = []
for i in range(m):
    kls.append(list(map(int,input().split())))
pls = list(map(int,input().split()))
#print(kls)
#print(pls)
ans = 0 #答え
for j in range(2**n): #スイッチの点灯状態を表す
    cnt = 0 #点灯している電球の数のカウント
    for h in range(m): #電球の数だけループをまわす
        cnts = 0 #onスイッチの数のカウント
        for y in kls[h][1:]: #電球に接続されているスイッチの数だけループをまわす
            #print(y)
            if (((j >>(y-1))) & 1): #bit全探索スイッチ番号ー１だけずらして判定
                #print(((j >>(y-1))) & 1)
                cnts += 1
        if cnts%2 == pls[h]: #スイッチの個数を2で割った余りが等しい
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ds = []
for _ in range(M):
  itr = map(int, input().split())
  k = itr.__next__()
  s = [ i-1 for i in itr]
  ds.append((k, s))

ds = [ (d[0], d[1], p) for d, p in zip(ds, map(int, input().split()))]

cnt = 0
for i in range(2**N):
  state = format(i, 'b').zfill(N)
  lights_up = True
  for k, ss, p in ds:
    s_on = 0
    for s in ss:
      if state[s] == '1':
        s_on += 1
    if s_on%2 != p:
      lights_up = False
      break
  if lights_up:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    n, m = [int(i) for i in input().split()]
    s = []
    # 接続グラフ
    # i 番目のスイッチには 電球との接続情報が入っている
    a = [0 for i in range(n)]
    for j in range(m):
        k, *switch = [int(i) for i in input().split()]
        for s in switch:
            a[s-1] |= (1 << j)
    p = int(("".join(reversed([i for i in input().split()]))), base=2)

    ans = 0
    # 全探索
    for i in range(1<<n):
        t = 0
        for j in range(n):
            if (i >> j & 1) == 1:
                t ^= a[j]
        if t == p:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

li = []
new_li = []

for i in range(2**n):
  i_bin = format(i, 'b').zfill(n)
  li.append(i_bin)
  
S = []
for i in range(m):
  s = list(map(int,input().split()))[1:]
  S.append(s)
   
p = list(map(int,input().split()))

for i in range(m):
  for j in li:
    count = 0
    for k in S[i]:
      count += int(j[k-1])
    if count % 2 == p[i]:
      new_li.append(j)
  li = new_li
  new_li = []
      
print(len(li)) #answer

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

ans = 0
for i in range(1<<N):
  for j, k in enumerate(S):
    if sum(1 for kj in k if (i>>(kj-1) & 1))%2 != P[j]:
      break
    if j == len(S)-1:
      ans += 1

print(ans)

Submission status: Accepted

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

res = 0
for i in range(2 ** n):
    l = []
    for j in range(n):
            l.append(int((i & (2 ** j)) == 0))
    flag = True
    
    for ll, j in enumerate(k):
        cnt = 0
        for q in j:
            cnt += l[q - 1]
        if cnt % 2 != p[ll]:
            flag = False

    if flag:
        res += 1
print(res)

Submission status: Accepted

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

def on(l):
    for i in range(m):
        _s = s[i]
        cnt = 0
        for j in _s:
            cnt += l[j-1]
        if not cnt%2==p[i]:
            return 0
    return 1

from itertools import product

ans = 0
for x in product([0, 1], repeat=n):
    ans += on(x)

print(ans)

Submission status: Accepted

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

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(m):
      a = list(int(i) for i in input().split())
      query.append(a)
  p = list(int(i) for i in input().split())
  #print(query)
  
  A = []
  for i in range(n):
    A.append(i+1)
    
  ans = 0
  #探索
  for i in range(1 << n):
    flag = 1
    output = []
    for j in range(n):
     if ((i >> j) & 1) == 1:
       output.append(A[j])

    for s in range(m): 
     if len(query)==0: 
      if not p[s] == 0:
        flag = 0
        break
     a = query[s]
     times = a[0]
     thischeck = 0
     for k in range(times):
       checker = a[k+1]

       if checker in output:
        thischeck += 1
       else:
        thischeck += 0
     if p[s] == thischeck%2:
       pass
     else:
       flag = 0
       break
  
    if flag:
      
      ans += 1
    else:
      pass
  print(ans)
solve()

Submission status: Accepted

Solution code:
# Technique often used
# enumerate: for i, a in enumerate(a_list):
# Functional Programming: filter, map, reduce

# naming conventions
# if [s_1, s_2, s_3, ..., s_k] then I name this list sk
# if [[s_11, s_12, ..., s_1k], ..,[s_j1, s_j2, ..., s_jk] then I name this list sjk
# if something strange in list then I add _ to list's name (ex:sjk_)

# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l

from itertools import combinations # https://docs.python.org/ja/3/library/itertools.html#itertools.combinations
from itertools import permutations # https://docs.python.org/ja/3/library/itertools.html#itertools.permutations
from collections import deque # https://docs.python.org/ja/3/library/collections.html#collections.deque
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
def gcds(a):
    if len(a)==1:
        return a[0]
    else:
        element = gcd(a[0], a[1])
        if len(a)==2:return(element)
        else:
            for i in range(2,n):
                element=gcd(element,a[i])
            return(element)
def debug_print(word,a,is_test=False):
    if is_test and not word:
        print("")
    elif is_test:
        print(word,a)
    else:
        pass

is_test = False
if is_test:
    n,m = [2, 2]
    smk_ = [[2, 1, 2],[1, 2]]
    pm = [0, 1]
else:        
    n,m = map(int,input().split())
    smk_ = [[int(i) for i in input().split()] for j in range(m)]
    pm = [int(i) for i in input().split()]

subsets=[]
# exclude empty set (think about it later)
for i in range(n):
    for c in combinations(range(n), i+1):
        subsets.append(c)
debug_print("subsets",subsets,is_test)

ans = 0
for subset in subsets:
    for i_m, sk_ in enumerate(smk_):
        counter = 0
        for sub in subset:
            debug_print("sub",sub,is_test)
            debug_print("sk_[1:]",sk_[1:],is_test)
            debug_print("pm[i_m]",pm[i_m],is_test)
            if sub + 1 in sk_[1:]:
                counter += 1
                debug_print("counter",counter,is_test)
            debug_print("","",is_test)
        if counter % 2 != pm[i_m]:
            debug_print("break: i_m=",i_m,is_test)
            break
    else:
        ans += 1

# think about empty set (if all switches are off)
if not(any(pm)):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    switchs = []
    for i in range(M):
        tmp = [int(x) for x in input().split()]
        switchs.append(tmp[1:])

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

    pattern = 0
    for i in range(2 ** N):
        on_state = [0] * N
        for j in range(N):
            if ((i >> j) & 1):
                on_state[(N-1) -j] = 1

        light_on = False
        for k_ in range(M):
            on_light_cnt = 0
            for switch in switchs[k_]:
                if on_state[switch-1] == 1:
                    on_light_cnt += 1

            if on_light_cnt % 2 != p[k_]:
                light_on = False
                break

            light_on = True

        if light_on == True and k_ == M-1:
            pattern += 1

    print(pattern)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, M =map(int,input().split())
coeff = np.zeros((M,N)) # M行N列のO行列を作成(行列の添字はそれぞれ０からであることに注意)
for i in range(M):
    input_list = list(map(int, input().split())) # 標準入力をint化し、listに入れる
    for j in input_list[1:]: # jにinput_list内の値をindex=1から代入、[1:]とすることでinputしたリストのサイズが変わっても対応
        coeff[i][j-1] = 1 # i行j-1列の値を1にする
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    vec = [int(num) for num in bin(i)[2:]] # iの２進表示を各桁に分けてベクトルとして保存
    fill = N - len(vec)
    vec = np.append(np.zeros(fill), np.array(vec)) # np.zeronos(fill)で0000, np.array(vec)で101101って感じ
    if(all(np.dot(coeff, vec) % 2 == p)):
        ans += 1
print(ans)

Submission status: Accepted

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

n, m = lmi()
s = [lmi() for i in range(m)]
p = lmi()
on = [0] * n
ans = 0
for i in range(1 << n):
    for j in range(n):
        on[j] = i%2
        i = i >> 1

    c = 0
    for j in range(m):
        wa = sum([on[x] for x in range(n) if x+1 in s[j][1:]])
        if wa%2 == p[j]:
            c += 1

    if c == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

switch = range(1,N+1)
pattern = [()]
for i in range(1,N+1):
    pattern.extend(tuple(itertools.combinations(switch, i)))
count = 0
for swp in pattern:
    for p, s in zip(P,S):
        match = len(set(s) & set(swp))
        if match % 2 != p:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
ans=0
n,m=map(int,input().split())
a=[]
k=[]
for i in range(m):
    a.append([int(j) for j in input().split()])
    a[i]=a[i][::-1]
    k.append(a[i].pop())
p=[int(j) for j in input().split()]

for i in range(2**n):
    s=[]
    for j in range(n):
        s.append((i>>j)%2)
    
    if all([sum([s[y-1] for y in a[j]])%2==p[j] for j in range(m)]):
        ans+=1

print(ans)

Submission status: Accepted

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

# print(k_array)

ans = 0
for i in range(2**N):
    switch_str = bin(i)[2:].zfill(N)
    # print(switch_str)
    for m in range(M):
        count = 0
        for k in k_array[m]:
            if switch_str[k - 1] == "1":
                count += 1
        if count % 2 != p_array[m]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

KS = []
ans = 0

for i in range(2**N):

    for j in range(M):
        Z = [0]*N
        bin_s = 0
        KS = KS_lis[j]
        K = KS[0]
        S = KS[1:]

        for l in range(K):
            bin_s += 2**(int(S[l])-1)

        if bin(i & bin_s).count("1") % 2 != P[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

result = 0

def check(i, j):
    x = sum((i >> (s - 1)) & 1 for s in KS[j][1:])
    return x % 2 == p[j]

for i in range(2**N):
    result += all(check(i, j) for j in range(M))

print(result)

Submission status: Accepted

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

for i in range(2**n):
    res+=1
    for j in range(len(arr)):
        on = 0
        for k in range(arr[j][0]):
            on += (i>>(arr[j][k+1]-1))%2
        if (on%2 != p[j]):
            res -=1
            break
print (res)

Submission status: Accepted

Solution code:
import sys
READ = lambda : sys.stdin.readline().strip().split()
READi = lambda : map(int, sys.stdin.readline().strip().split())

N, M = READi()
LINES = []
for i in xrange(M):
  LINES += [READi()]
P = READi()

count = 0
for i in xrange(2**N):
  bits = [(i>>b)&1 for b in xrange(N)]
  ok = True
  for line, p in zip(LINES, P):
    tmp = map(lambda x: bits[x-1], line[1:])
    ok &= (sum(tmp)%2) == p
  count += int(ok)
print count

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
from itertools import permutations
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
sw = []
count = 0
d = defaultdict(int)

for i in range(m):
    p = readl()
    sw.append(p[1:])
p = readl()
count = 0
for i in range(2 ** n):
    den = defaultdict(int)
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in sw[k]:
                    den[k] += 1
    flg = True
    for j in range(m):
        if den[j] % 2 != p[j]:
            flg = False
    if flg:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May 27 22:13:19 2019

@author: Yamazaki Kenichi
"""

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

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for bit in range(1<<N):
    now = [0 for i in range(M)]
    for i in range(N):
        if bit & 1<<i:
            for j in range(M):
                now[j] += S[j]//(1<<i)
    flg = True
    for j in range(M):
        if now[j]%2 != p[j]:
            flg = False
    ans += flg
print(ans)

Submission status: Accepted

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0
# N 個のスイッチの状態を N bit の二進数で表現する
for bit in range(2 ** N):
    flag = False
    # 電球につながってるスイッチを調べる
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            # 割り当てたスイッチの番目に bit が立っているかどうか調べる
            if (1 << (s - 1)) & bit:
                cnt += 1
        # 電球が点灯する条件ならそのまま次の電球へ
        if cnt % 2 == p[m]:
            continue
        # 点灯しなければ次の点灯候補（bit）を更新する
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Submission status: Accepted

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

def is_light(sw, p, state):
    acc = 0
    for s in sw:
        if ((state >> (s-1))& 1) == 1:
            acc += 1
    return acc % 2 == p


ans = 0
for i in range(1<<n):
    for j in range(m):
        if not is_light(ss[j], p[j], i):
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May 27 21:28:42 2019

@author: Yamazaki Kenichi
"""

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

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for i in range(2**N):
    flg = True
    for j in range(M):
        if ('{:010b}'.format(S[j]&i)).count('1') % 2 == p[j]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0
# N 個のスイッチの状態を N bit の二進数で表現する
for bit in range(2 ** N):
    flag = False
    # 電球につながってるスイッチを調べる
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            # 割り当てたスイッチの番目に bit が立っているかどうか調べる
            if (1 << (s - 1)) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Submission status: Accepted

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0
# スイッチの状態を N bit の二進数で表現する
for bit in range(2 ** N):
    flag = False
    # 電球につながってるスイッチを調べる
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            if (1 << (s - 1)) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Submission status: Accepted

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

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

p = list(map(int, input().split()))
    
cnt = 0
    
for i in range(2**n):
    bin_i = "{:010b}".format(i)[::-1]
    
    for j in range(m):
        ks = kss[j]
        k = ks[0]
        s = ks[1:]
        
        sum_s = 0
        
        for x in range(k):
            sum_s += int(bin_i[s[x]-1])
            
        if sum_s % 2 != p[j]:
            break
    else:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
connect = []
for j in range(M):
    connect.append(list(map(int, input().split())))
plist = list(map(int, input().split()))

count = 0
for n in range(2**N):
  for j in range(M):
    connect_score = sum(2**(np.array(connect[j][1:])-1))
    switch_on = n & connect_score
    num_switch_on = [int(k) for k in str(bin(switch_on))[2:]]
    if (sum(np.array(num_switch_on)) % 2) != plist[j]:
  		 break
    if j == M-1:
        count += 1
  
print(count)

Submission status: Accepted

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0
for bit in range(2 ** N):
    flag = False
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            if 1 << (s - 1) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Submission status: Accepted

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

#入力: 電球iについての情報
lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a]
#入力: どのような情報であればOKかのリスト
p = list(map(int, input().split()))

# print ('lst', lst)

#計算部分
ans = 0 #全探索用の答え
for i in range(2 ** N): #1をon, 0をoffとする2bit
    #最大でもスイッチは10桁＋2進数であることを表す部分2桁
    a = format(i, '012b')
    #2進数をリストとして保存, 前2桁は2進数であることを表す部分のため不要 
    lst2 = list(a[2:]) #右からスイッチ1, 2, ... Nと逆順になっていることに注意
    # print ('lst2', lst2)
    #あるスイッチの付け方が題意を満たしているか判断するフラグ
    flag = True 
    l = 0 #電球番号-1(リストのため)
    for j in lst: #i番目のスイッチの繋がっていることの情報
        # print ('j[1:]', j[1:])
        count = 0 #ONのスイッチの個数を数える
        for k in j[1:]: #s_i番目のスイッチの状態を読み出す、最初の一桁はスイッチの数
            # print ('k', k)
            if lst2[9-k+1] == '1': #ONの時、カウントを増やす
                count += 1
                # print ('B')
        # print ('count', count)
        # print ('p[l]', p[l])
        if count%2 != p[l]: #ONになっているスイッチの数//2が題意を満たしているかを判断
            flag = False #題意を満たしていなかったらフラグをFalseにする
            # print ('C')
        l += 1 #電球番号を一つ増やす
    if flag: #全ての電球を確認して、フラグがまだTrueなら答えを+1
        ans += 1
        # print ('A')

print (ans)

Submission status: Accepted

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

for s in range(1<<n):
    tmp = 0
    for i in range(len(Q)):
        cnt = 0
        for t in Q[i]:
            if s>>(t-1) &1 == 1:
                cnt += 1
        if cnt % 2 == P[i]:
            tmp += 1
    if tmp == m:
        res += 1
print(res)

Submission status: Accepted

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

lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a]
p = list(map(int, input().split()))

# print ('lst', lst)
ans = 0
for i in range(2 ** N): #1をon, 0をoffとする2bit
    a = format(i, '012b')
    lst2 = list(a[2:])
    # print ('lst2', lst2)
    flag = True
    l = 0
    for j in lst:
        # print ('j[1:]', j[1:])
        count = 0
        for k in j[1:]:
            # print ('k', k)
            if lst2[9-k+1] == '1': #ONの時、カウントを増やす
                count += 1
                # print ('B')
        # print ('count', count)
        # print ('p[l]', p[l])
        if count%2 != p[l]:
            flag = False
            # print ('C')
        l += 1
    if flag:
        ans += 1
        # print ('A')
    

print (ans)