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())
a = [0] * m

for i in range(m):
    k, *s = list(map(int, input().split()))
    for j in range(k):
        a[i] += 2**(s[j] - 1)

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

count = 0
for i in range(2**n):
    flg = True
    for j in range(m):
        if bin(i & a[j]).count("1") % 2 != p[j]:
            flg = False
            break
    if flg:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
s = [0] * m

for i in range(m):
    x = list(map(int, input().split()))
    for j in range(x[0]):
        s[i] += 2**(x[1+j] - 1)

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

count = 0
for i in range(2**n):
    flg = True
    for j in range(m):
        if bin(i & s[j]).count("1") % 2 != p[j]:
            flg = False
            break
    if flg:
        count += 1

print(count)

Submission status: Accepted

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

k = []
s = []

for _ in range(M):
    tmp = tuple(map(int, input().split()))
    k.append(tmp[0])
    s.append(set(tmp[1:tmp[0] + 1]))

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

# print(k, s, p, sep="\n")

ans = 0

for i in range(2 ** N):
    # 各iでonになっている電球の数
    light_on = 0

    # 電球jについて
    for j in range(M):
        switch_on = 0

        for k in range(N):
            # onになっているスイッチが
            if (i >> k) & 1:
                # 電球jとつながっているものならカウント
                if k + 1 in s[j]:
                    switch_on += 1

        # onになっているスイッチの個数がp[j]に等しいなら電球jは点灯している
        if switch_on % 2 == p[j]:
            light_on += 1

    # 全ての電球が点灯しているならカウント
    if light_on == M:
        # print(bin(i))
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# ABC128C

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

cnt=0
for bit in range(2**N):
    c=1
    for i in range(M):
        ons=0
        for j in range(ks[i][0]):
            k=ks[i][j+1]-1
            if (bit>>k & 1):
                ons+=1
        if ons % 2 != ps[i]:
            c*=0
            break
    if c==1:
        cnt+=1
print(cnt)

Submission status: Accepted

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

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

ans = 0
temp = [0]*N
for i in range(2**N):
    # bit全探索のつもり
    for j in range(N):
        if((i >> j) & 1):
            temp[j] = 1
    # print("temp = ", temp)

    for k in range(M):
        count = 0
        for l in range(1, len(S[k])):
            if temp[S[k][l] - 1] == 1:
                count += 1
        if count % 2 != p[k]:
            break
    else:
        ans += 1
    temp = [0]*N

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

# スイッチが付いているか付いていないかを表す集合
ans = 0
for bit in itertools.product([0, 1], repeat=N):
    for d, p in zip(data, P):
        cnt = 0
        for i in d[1:]:
            if bit[i - 1] == 1:
                cnt += 1
        if cnt % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

s = [0] * m

for i in range(m):
    k, *li = map(int, input().split())
    for j in range(k):
        s[i] += 2**(li[j]-1)

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


ans = 0

for i in range(2**n):
    tmp = True
    for j in range(m):
        if bin(i & s[j]).count("1") % 2 != p[j]:
            tmp = False
            break

    if tmp:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
a=""
sw=[]
pattern=[]
def bit(i,turn):
    if i==N:
        pattern.append(list(turn))
    else:
        bit(i+1,turn+"0")
        bit(i+1,turn+"1")
for i in range(M):
    k=list(map(int,input().split()))
    sw.append(k)
hantei=list(map(int,input().split()))
bit(0,a)
count=0
ans=0
for i in pattern:
    sw_list=[0]*(N+1)
    for j in range(M):
        k=sw[j]
        for l in k[1:]:
            if i[l-1]=="1":
                sw_list[j]+=1
    for m in range(M):
        if sw_list[m]%2!=hantei[m]:break
    else:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[-1]*n for _ in range(m)]
for i in range(m):
  s = list(map(int, input().split()))
  s.pop(0)
  for j in s:
    g[i][j-1] = 1
p = list(map(int, input().split()))

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

print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    state = np.zeros((m,n),dtype=int)
    for i in range(m):
        ks = list(map(int,ipt().split()))
        for j in ks[1::]:
            state[i][j-1] = 1
    p = [int(i) for i in ipt().split()]
    ans = 0
    fm = "0"+str(n)+"b"
    for i in range(2**n):
        li = np.array(list(map(int,format(i,fm))))
        for i,si in enumerate(state):
            if not np.count_nonzero(li&si)%2 == p[i]:
                break
            if i == m-1:
                ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

ans = 0

for i in range(2**n):
    i_bin = bin(i)[2:].zfill(n)
    flag = 1
    for j in range(m):
        cnt = 0
        for k in s[j]:
            if i_bin[k - 1] == "1":
                cnt += 1
        if cnt % 2 != p[j]:
            flag = 0
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(2 ** N):
    flg = True
    for j, row in enumerate(array):
        count = 0
        for k in row[1:]:
            if i & (1 << (k - 1)):
                count += 1
        if not p[j] % 2 == count % 2:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
li = [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):
    x = 0 #点灯してるかしてないか
    y = [[] for j in range(m)]
    for j in range(n):
        if ((i >> j) & 1): #フラグが立っていたら=スイッチon 
            for k in range(m):
                if j+1 in li[k]:
                    y[k].append(j+1)
    for j in range(m):
        if len(y[j]) %2 == p[j]:
            x += 1                   
    if x == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

input = sys.stdin.readline


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

    ans = 0
    for comb in product(range(2), repeat=N):
        are_on = True
        for i in range(M):
            n_on = 0
            for ss in s[i]:
                n_on += 1 if comb[ss - 1] == 1 else 0
            if n_on % 2 != p[i]:
                are_on = False
        ans += 1 if are_on else 0

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def get_subsets(fullset):
  listrep = list(fullset)
  subsets = []
  for i in range(2**len(listrep)):
    subset = []
    for k in range(len(listrep)):            
      if i & 1<<k:
        subset.append(listrep[k])
    subsets.append(subset)        
  return subsets

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

ans = 0
subsets = get_subsets(set(range(1, n+1)))
for ss in subsets:
    ss = set(ss)
    b = False
    for idx in range(m):
        pat = set(mat[idx][1:])
        if len(pat&ss)%2 != ps[idx]:
            b = True
            break
    if not b:
       ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m=map(int,input().split())
count=0

switch_list_all=[None]*n
for i in range(n):
    switch_list=[0]*m
    switch_list_all[i]=switch_list

for i in range(m):
    lst=list(map(int,input().split()))
    for j in range(len(lst)-1):
        switch_list_all[lst[j+1]-1][i]+=1
        

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

a_list=list(itertools.product([0,1],repeat=n))


for i in range(len(a_list)):
    a=a_list[i]
    point=[0]*m
    c=0
    for z in range(m):
        point[z]+=p[z]
    for j in range(n):
        s_list=switch_list_all[j]
        if a[j]==1:
            for x in range(m):
                point[x]+=s_list[x]
    for y in range(m):
        if point[y]%2==0:
            c+=1
    if c==m:
        count+=1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M = map(int, input().split())
L = []
S = [np.array([0 for _ in range(M)]) for _ in range(N)]

for _ in range(M):
  l = list(map(int, input().split()))
  L.append(l)

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

l = 0
for s in L:
  l += 1
  for i in range(s[0]):
    S[s[1+i]-1][l-1] += 1

for T in itertools.product([1,0], repeat = N):
  Flag = True
  ans = np.zeros(M)
  for i in range(N):
    if T[i] == 1:
      ans += S[i]
  for j in range(M):
    if ans[j] % 2 != P[j]:
      Flag = False
  if Flag:
    cnt += 1

print(cnt)

Submission status: Accepted

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

def dfs(n, sw):
  if n > 0:
    return dfs(n-1, sw + [0]) + dfs(n-1, sw + [1])
  else:
    answer = 1
    for m in range(M):
      count = 0
      for k in range(K[m]):
        count += sw[S[m][k]-1]
      if count % 2 != P[m]:
        answer = 0
        break
    return answer
        
print(dfs(N, []))

Submission status: Accepted

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

res = 0
for i in range(2**N):#bit全探索開始
    switch = [0]*N
    for j in range(N):
        if (i >> j) & 1:
            switch[j] = 1
    light_cnt = 0 #点灯しているライトの数
    for j in range(M): #スイッチの情報から転倒するものを探索
        cnt = 0 #ライト_jにおいて押されているスイッチの数
        for k in range(1,switch_inf[j][0]+1):
            if switch[switch_inf[j][k]-1]:
                cnt += 1
        if cnt%2 == p[j]:
            light_cnt += 1
    if light_cnt == M:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks=[list(map(int, input().split()))[1:] for _ in range(m)]
ps = list(map(int, input().split()))
#print(ks)
res=0
perms=[]
for i in range(2**n):
    list2 = []
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(1)
        else:
            list2.append(0)
    perms.append(list2)
    ons=0
    for idx,p in enumerate(ps):
        cnt=0
        for k in ks[idx]:
            if list2[k-1]==1:
                cnt+=1
        if cnt%2==p:
            ons+=1
    if ons==m:
        res+=1
print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [0]*n
for i in range(m):
    k = list(map(int,input().split()))
    for j in range(1,k[0]+1):
        s[k[j]-1] |= 1<<i
p=0
k = list(map(int,input().split()))
for i in range(m):
    p |= k[i]<<i
ans = 0
for i in range(1<<n):
    t = 0
    for j in range(n):
        if i>>j&1: t^=s[j]
    if t==p: ans+=1
print(ans)

Submission status: Accepted

Solution code:
# input
N, M = map(int, input().split())
connect_nums = []
data = []
for i in range(M):
  tmp = list(map(int, input().split()))
  connect_nums.append(tmp.pop(0))
  data.append(tmp)
switch_conditions = list(map(int, input().split()))

# main
ans = 0
for i in range(2**N):
  on_switches = []
  for j in range(N):
    if ((i >> j) & 1):
      on_switches.insert(0, 1)
    else:
      on_switches.insert(0, 0)
      
  ansflag = True
  
  for l in range(M):
    oncnt = 0
    for ss in data[l]:
      if on_switches[ss-1] == 1:
        oncnt += 1
    if oncnt % 2 != switch_conditions[l]:
      ansflag = False
      break
  
  if ansflag:
    ans += 1
    
# output
print(ans)

# debug
"""
print(N, M)
print(connect_nums, switch_conditions)
print(data)
"""

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 10:46:22 2020

@author: NEC-PCuser
"""

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

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

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

count = 0;
for i in range(0, 2**N):
    switch = [0] * N
    for j in range(0, N):
        if ((i >> j) & 1):
            switch[j] = 1
    k = 0
    for p_split in p:
        t = 0
        for s_split in s[k]: 
            if (switch[s_split - 1]):
                t += 1
        if (t % 2 != p_split):
            break
        else:
            k += 1
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
def check(sw, p, list):
    count = 0
    res = 0
    # print(list)
    for i in range(len(sw)):
        count = 0
        for j in range(sw[i][0]):
            # print(str(sw[i][j+1]) + "  " + str(list) + "  " + str(sw[i][j + 1] in list))
            if(sw[i][j + 1] in list):
                count += 1
        if count % 2 == p[i]:
            res += 1
    # print(count)
    return res == len(sw)

n,m = map(int,input().split())
sw = []

for i in range(m):
    sw.append(list(map(int,input().split())))
    # print()
    # print(sw[i])
p = list(map(int,input().split()))
res = 0
# print(p)

for i in range(2**n):
    list = []
    for j in range(n):
        if(i >> j) & 1 == 1:
            list.append(j+1)
    if(check(sw,p,list)):
        res += 1
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
slist = []
for _ in range(M):
    k, *s = list(map(int, input().split()))
    slist.append(set(s))
plist = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    on = set()
    pika = 0
    for j in range(N):
        if ((i >> j) & 1):
            on.add(j+1)
    for lamp_num in range(M):
        if len(slist[lamp_num]&on)%2 == plist[lamp_num]:
            pika += 1
    if pika == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

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

# 全探索だ
ans = 0
for switch in list(itertools.product([0, 1], repeat=N)):
    ok = 0
    for denkyu in range(M):
        tmp = 0
        for i in s[denkyu][1:]:
            tmp += switch[i-1]
        if(tmp % 2 == p[denkyu]):
            ok += 1
    if (ok == M):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int, input().split())
s = [list(map(lambda x: int(x) - 1, input().split()[1:])) for _ in range(m)]
p = list(map(int, input().split()))
print(sum(all(sum(b[ki] for ki in s[i]) % 2 == p[i] for i in range(m)) for b in product((True, False), repeat=n)))

Submission status: Accepted

Solution code:
#C
n,m = map(int,input().split())
denkyu = []
for _ in range(m):
    tmp = list(map(int,input().split()))
    denkyu.append(tmp)   
p = list(map(int,input().split()))

#bit全探索？
import itertools
switch = list(itertools.product([0,1],repeat=n))
cnt = 0

for i in switch:
    gokei = 0
    flg = True
    for j in range(m):
        gokei = 0
        for k in range(1,len(denkyu[j])):
            gokei += i[denkyu[j][k]-1] 
            
        if gokei % 2 != p[j]:
            flg = False
            break
            
    if flg:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
n_switch, n_lamp = map(int,input().split())
lamp_switch_count = [0] * n_lamp
lamp_switch = [0] * n_lamp

for i in range(n_lamp):
    ls = list(map(int, input().split()))
    lamp_switch_count[i] = ls[0]
    ls_switch = ls[1:]
    for j in range(len(ls_switch)):
        ls_switch[j] -= 1
    lamp_switch[i] = ls_switch

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

ans = 0
for pattern in range(2**n_switch):
    all_on = True
    switch_on_ls = [0] * n_switch 
    for i_switch in range(n_switch):
        if (pattern >> i_switch) & 1:
            switch_on_ls[i_switch] = 1
    for i_lamp in range(n_lamp):
        num_target = lamp_switch_count[i_lamp]
        onswitch_num = 0
        for i in range(num_target):
            ind_of_target_switch = lamp_switch[i_lamp][i]
            if switch_on_ls[ind_of_target_switch]:
                onswitch_num += 1
        if onswitch_num % 2 != mod_ls[i_lamp]:
            all_on = False
    if all_on:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt=0

for i in range(2**N):
    for k in range(M):
        tmp=0
        for j in range(N):
            if ((i >> j) & 1) and j+1 in s[k]:
                tmp+=1
        if tmp%2!=p[k]:
            break
    else:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
    ptn = bin(i)[2:].rjust(N, "0")  # N桁の2進表現にする,さらに0を足している（左に）
    light = True  # 着目している電球が点灯していないときはこれがFalseになる
    for j in range(M):
        tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
        for n in range(1, s[j][0] + 1):
            if ptn[s[j][n] - 1] == "1":
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def AreAllTheLightsOn(SwitchPattern,M,LineVolume,Destinations,p):
    # print(SwitchPattern)
    Light=0
    for m in range(M):
        OnSwitch=0
        for l in range(LineVolume[m]):
            a=Destinations[m][l]-1
            if SwitchPattern[a]==1:
                OnSwitch += 1
            else:
                pass
        if OnSwitch%2==p[m]:
            Light+=1
    # print (Light)
    if Light==M:
        return True


N,M=map(int,input().split())
K=[]
for _a in range (M):
    arr=list(map(int,input().split()))
    K.append(arr)
LineVolume=[] #m番目の電球がスイッチとつながっている線の数
Destinations=[] #m番目の電球がつながっているスイッチの番号(1スタート)
for _b in range (M):
    LineVolume.append(K[_b][0])
    Destinations.append(K[_b][1:])
p=list(map(int,input().split()))
# print (LineVolume)
# print (Destinations)
# print(p)

LightOnPattern=0

for Pattern in range (2**N):
    SwitchPattern=[]
    for ONOFF in range(N):
        if(Pattern>>ONOFF)&1==1:
            SwitchPattern.append(1)
        else:
            SwitchPattern.append(0)
    # print(SwitchPattern)
    if AreAllTheLightsOn(SwitchPattern,M,LineVolume,Destinations,p)==True:
        LightOnPattern += 1

print(LightOnPattern)

Submission status: Accepted

Solution code:
# 入力
n, m = map(int, input().split())
s = [[] for i in range(m)]
for i in range(m):
    lines = [int(k) for k in input().split()]
    for j in range(1, len(lines)):
        s[i].append(lines[j] - 1)
p = [int(i) for i in input().split()]

# 処理
ans = 0
for i in range(1 << n):  # 2 ** n でも同じ
    switches = [0] * n  #
    flag = True
    for j in range(n):  # switchesリストの作成(全てのスイッチの状態を列挙)
        if (i >> j) & 1:  # iをj回右にシフトして1と論理積をとる(最下位の桁が1かcheck)
            switches[j] = 1
    for k in range(m):  # 行
        cnt = 0  # ついているスイッチの数
        for t in range(len(s[k])):  # 列
            if switches[s[k][t]] == 1:
                cnt += 1
        if cnt % 2 != p[k]:  # 等しいときにTrue
            flag = False
            break  # p_iの条件を満たさないので次の行へ
    if flag:  # 全ての電球が点灯する
        ans += 1

# 出力
print(ans)

Submission status: Accepted

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

ary = []
for i in range(m):
	x = list(map(int, input().split()))
	x.pop(0)
	ary.append(x)

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

cnt = 0
for i in range(2**n):
	den = [0 for ii in range(n)]
	for j in range(n):
		if (i>>j) & 1:
			den[j] += 1
	flg = False
	for j in range(m):
		c = 0
		d = [0 for i in range(n)]
		for k in ary[j]:
			if den[k-1] == 1:
				d[k-1] = 1
		for kk in d:
			if kk == 1:
				c += 1
		'''
		for k in ary[j]:
			if den[k-1] ==1:
				c += 1
		'''
		if c%2 == p[j]%2:
			continue
		else:
			flg = True
			break
	if flg == False:
		cnt += 1
print (cnt)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
def main():
    N, M = map(int, input().split())
    s = [[] for i in range(M)]
    for i in range(M):
        lines = [int(k) for k in input().split()]
        for j in range(len(lines)):
            if j == 0:
                continue
            s[i].append(lines[j] - 1)
    p = [int(i) for i in input().split()]
    ans = 0
    for i in range(1 << N):
        switchs = [0] * N
        flag = True
        for j in range(N):
            if (i >> j) & 1:
                switchs[j] = 1
        for k in range(M):
            count = 0
            for t in range(len(s[k])):
                if switchs[s[k][t]] == 1:
                    count += 1
            if count % 2 != p[k]:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  for x,y in zip(s, p):
    flag = False
    for a in x:
      if i & 1 << (a-1):
        flag = not flag
    if int(flag) != y:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

k=[]
s=[]
for i in range(m):
    templist=[int(x)-1 for x in input().split()]
    k.append(templist[0]+1)
    s.append(templist[1:])

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

b=[] #全部の可能性
for i in range(2**n):
    temp=[]
    for j in range(n):
        if (i>>j)&1==1:
            temp.append(1)
        else:
            temp.append(0)
    b.append(temp)

ans=0
for x in b:
    cnt=0
    for i in range(m):
        temp=0
        for j in range(len(s[i])):
            temp+=x[s[i][j]]
        if temp%2 != p[i]:
            continue
        else:
            cnt+=1
            if cnt==m:
                ans+=1
print(ans)

Submission status: Accepted

Solution code:

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

ans = 0

lis = [ [] for i in range(N) ]

for i in range(M):

    tmp = list(map(int,input().split()))
    tmp = tmp[1:]

    for j in tmp:
        lis[j-1].append(i)

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

for i in range(2**N):

    now = [0] * M

    for j in range(N):
        if i & (2**j) > 0:
            for k in lis[j]:
                now[k] += 1

    flag = True
    for i in range(M):
        if now[i] % 2 != p[i]:
            flag = False
            break
    if flag:
        ans += 1

print (ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ks=[]
for _ in range(m):
	rr=list(map(int,input().split()))
	ks.append(rr)
p=list(map(int,input().split()))
def two(x):
	return "0"*(n-len(bin(x)[2:]))+bin(x)[2:]
ans=0
for i in range(2**n):
	r=two(i)
	f=1
	for j in range(m):
		cnt=0
		for k in range(ks[j][0]):
			if r[ks[j][k+1]-1]=="1":
				cnt+=1
		if cnt%2!=p[j]:
			f=0
			break
	ans+=f
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = []
for _ in range(M):
    t , *s = map(int,input().split())
    S.append(s)
P = list(map(int,input().split()))
answer = 0

for i in range(1 << N):
    switch = [0] * N
    
    for j in range(N):
        if (i >> j) & 1:
            switch[j] = 1
    
    for k in range(M):
        cnt = 0
        for l in range(N):
            if switch[l]:
                if (l+1) in S[k]:
                    cnt += 1
        if cnt % 2 != P[k]:
            break
    else:
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
import itertools

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

ans=0
for bit in itertools.product((0,1),repeat=n):
    for i in range(m):
        count = sum(bit[id] for id in s[i])
        if count%2!=p[i]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
S = []
for i in range(m):
    k,*s = map(int,input().split())
    S.append(s)
P = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j) & 1:
            switch[j] = 1
    for k in range(m):
        cnt = 0
        for l in range(n):
            if switch[l]:
                if (l+1) in S[k]:
                    cnt += 1
        if cnt%2 != P[k]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

import itertools
import numpy as np

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

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

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

# print(ks)
ans = 0
for i in itertools.product([0, 1], repeat=n):
    i = np.array(i)
    flag = 1

    for j in range(len(ks)):
        ks_tmp = np.array(ks[j])
        if np.sum(np.take(i, ks_tmp[1:]-1)) % 2 == p[j]:
            continue
        else:
            flag = 0
            break
    if flag == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

count = 2 ** N
for i in range(2 ** N):
    switch_state = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            switch_state[j] = 1
    for m in range(M):
        point = 0
        for s in switch[m]:
            point += switch_state[s-1]
        if point %2 != P[m]:
            count -= 1
            break
print(count)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
# n: switch,    m: lamp
data = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

# O(100*(2**10))なので、全探索も容易なはず
ans = 0
for i in itertools.product([0, 1], repeat=n):  # パターンごと
    flag = True
    for j, val in enumerate(p):
        # 全てのランプがONなら、ans += 1
        # i = [0,1,1,1,1, ]
        tar = data[j]
        num = tar[0]
        count = 0
        for k in range(num):
            pick = tar[k + 1]
            count += i[pick - 1]
        # print(count)
        if (count % 2 == val):
            pass
        else:
            flag = False

    if (flag is True):
        ans += 1
    else:
        pass


print(ans)

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):#-1に注意（スイッチxはOnOff[x-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
    #全ての電球が点くならばansに+1
    if(flag==len(p)):
        ans+=1
print(ans)