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:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k.append(l[0])
        s.append(l[1:])
    p = list(map(int, input().split()))

    return N, M, k, s, p


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数(1 <= N <= 10)
        M (int): 電球の数(1 <= M <= 10)
        s (list): 電球と繋がっているスイッチ(1 <= s_ij <= N)
        p (list): 点灯判定(0または1)
    """
    # 求解処理
    ans = 0
    for bit in range(1 << N):
        is_all_light_on = True
        for m in range(M):
            on_count = 0
            for s_i in s[m]:
                if ((bit >> (s_i - 1)) & 1):
                    on_count += 1
            if on_count % 2 != p[m]:
                is_all_light_on = False
                break
        if is_all_light_on:
            ans += 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, k, s, p = get_input()

    # メイン処理
    main(N, M, s, p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, M = list(map(int, input().split()))
k, s = [], []
for m 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 bit in range(1 << N):
    is_light_on = True
    for m in range(M):
        on_count = 0
        for s_i in s[m]:
            if ((bit >> (s_i - 1)) & 1):
                on_count += 1
        if on_count % 2 != p[m]:
            is_light_on = False
            break
    if is_light_on:
        ans += 1

# 結果出力
print(ans)

Submission status: Accepted

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

for i in range(1<<N):
    onoff = bin(i)[2:].zfill(N)
    for j, switches in enumerate(lights):
        if sum(onoff[s-1] == '1' for s in switches[1:]) % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(1<<N):
    for j,lst in enumerate(connected):
        count = 0
        for s in lst[1:]:
            if (i>>(s-1)) & 1:
                count += 1
        if count % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(1<<N):
    on = 0
    onoff = bin(i)[2:].zfill(N)
    for j, switches in enumerate(lights):
        if sum(onoff[s-1] == '1' for s in switches[1:]) % 2 == p[j]:
            on += 1
    if on == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(tuple(map(int, input().split())))
P = tuple(map(int, input().split()))
import itertools
def hantei(A, RETU, P):
    for i in range(len(A)):
        count = 0
        for k in RETU:
            if k in A[i][1:]:
                count += 1
        if not count % 2 == P[i]:
            return False
    return True
ans = 0
for i in range(1, N + 1):
    for k in itertools.combinations(range(1, N + 1), i):
        if hantei(A, k, P):
            ans += 1
if hantei(A, [0], P):
    ans += 1
print(ans)

Submission status: Accepted

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

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

    k.append(int("".join(map(str, s)), 2))

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

def count1s(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n >>= 1

    return cnt

cnt = 0
for i in range(2**n):
    sol = True
    for j in range(m):
        if count1s(i & k[j]) % 2 == p[j]:
            pass
        else:
            sol = False
            break

    if sol:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
sp = [list(map(int, input().split())) for _ in range(m + 1)]
print(sum(all(sum(i[a - 1] for a in s[1:]) % 2 == p for s, p in zip(sp[:m], sp[-1])) for i in product((0, 1), repeat=n)))

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
print(sum(all(sum(i[b - 1] for b in a[1:]) % 2 == x for a, x in zip(s, p)) for i in product((0, 1), repeat=n)))

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    a, *b = map(int, input().split())
    k.append(a)
    s.append(b)
p = list(map(int, input().split()))
print(sum(all(sum(i[b - 1] for b in a) % 2 == x for a, x in zip(s, p)) for i in product((0, 1), repeat=n)))

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    a, *b = map(int, input().split())
    k.append(a)
    s.append(b)
p = list(map(int, input().split()))
print(
    sum(
        all(sum(i[b - 1] for b in a) % 2 == x for a, x in zip(s, p))
        for i in product((0, 1), repeat=n)
    )
)

Submission status: Accepted

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

ans=0
for i in range(1<<N):
  sw=[False]*M
  for j in range(M):
    cnt=0
    for k in range(1,len(S[j])):
      if (i>>(S[j][k]-1))&1:
        cnt+=1
      else:
        flag=0
    if cnt%2==P[j]:
      sw[j]=True
  if all(sw):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
K = [list(map(int, input().split())) for _ in range(m)]
P = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    flag = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            flag[j] = True
    on = [False] * m
    for j in range(m):
        sw = 0
        for k in range(1, K[j][0] + 1):
            if flag[K[j][k] - 1]:
                sw += 1
        if sw % 2 == P[j]:
            on[j] = True
    if False not in on:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int, input().split())
k=[list(map(int, input().split())) for i in range(m)]
p=list(map(int, input().split()))
bit=list(itertools.product([0,1], repeat=n))
ans=0
for i in bit:
  cnt=0
  for j in range(m):
    cnt2=0
    for l in range(1,k[j][0]+1):
      if i[k[j][l]-1]==1:
        cnt2+=1
    if cnt2%2==p[j]:
      cnt+=1
  if cnt==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[[int(i) for i in input().split()] for j in range(m)]
p=[int(i) for i in input().split()]
ans=chk=0
for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if i&1: l[j]=1
        i=i>>1
    y=0
    for j in range(m):
        x=0
        for a in range(k[j][0]):
            if l[k[j][a+1]-1]==1: x+=1
        if x%2==p[j]%2: y+=1
    if y==m: ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s = [list(map(int,input().split())) for i in range(M)]
p = list(map(int,input().split()))
l = [False] * (N+1) #l[1] is True when lightbulb 1 is on and False when off
ans = 0
for i in range(2**N):
    for j in range(N):
        if ((i >> j)&1):
            l[j+1] = True
        else:
            l[j+1] = False
    for k in range(M):
        cnt = 0
        for m in range(1,s[k][0]+1):
            if l[s[k][m]] == True:
                cnt += 1
        if cnt % 2 != p[k]:
            break
        if k == M-1:
            ans += 1
print(ans)

Submission status: Accepted

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

    for i in range(2 ** N):  # スイッチの状態をビット全探索
        switch = [0] * N
        flag = True

        for j in range(N):  # スイッチの状態を1パターン決める 1:ON, 0:OFF
            if ((i >> j) & 1):
                switch[j] = 1

        for j in range(M):  # 各電球について条件を満たすか確認
            cnt = 0  # 各電球についてonになっているスイッチの数
            for k in lst[j][1:]:
                if switch[k - 1] == 1:
                    cnt += 1

            if cnt % 2 != p[j]:  # 1つでも点灯しない電球があったら現在のスイッチの状態はだめ
                flag = False
                break

        if flag == True:  # すべての電球が点灯する
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = list(map(int, input().split(" ")))
    k_list = []
    s_list = []
    for _ in range(m):
        s = []
        for i, one in enumerate(input().split(" ")):
            if i==0:
                k = int(one)
            else:
                s.append(int(one))
        k_list.append(k)
        s_list.append(s)
    p = list(map(int, input().split(" ")))

    cnt = 0
    for x in range(2**n):
        f = 0
        onoff_list = [1 if bin(x)[2:].zfill(n)[i]=="1" else 0 for i in range(n)]
        for mi in range(m):
            s = s_list[mi]
            on_num = sum([onoff_list[si-1] for si in s])
            if on_num%2==p[mi]:
                f+=1
            else:
                break
        if f==m:
            cnt+=1
    print(cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

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

ans = 0
fmt = "{:0" + str(N) + "b}"
for i in range(2**N):
    valid = True
    d = list(map(int, list(fmt.format(i))))
    for j in range(M):
        if not P[j] == sum([d[k - 1] for k in K[j][1:]]) % 2:
            valid = False
            break
    if valid:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
s=[]
for i in range(m):
    s.append(lmp())
p=lmp()
ans=0
for i in range(2**n):#全てのスイッチの入れ方
    ans+=1
    for j in range(m):#全ての電球に対するチェック
        c=0
        for k in range(1,s[j][0]+1):#各電球に対するチェック
            if ((i>>(s[j][k]-1)) & 1):
                c+=1
        if (c-p[j])%2==1:
            ans-=1
            break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import product
n,m=map(int,input().split())
ks=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
count=0
for i in product([0,1],repeat=n):
    for j in range(m):
        
        temp=0
        for k in range(ks[j][0]):
            if i[ks[j][k+1]-1]==1:
                temp+=1
        if temp%2!=p[j]:
            break
    else: 
        count+=1
print(count)

Submission status: Accepted

Solution code:
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m=map(int,input().split())
k=[]
s=[]
for _ in range(m):
	tmp=input_array()
	k.append(tmp[0])
	s.append(tmp[1:])
p=input_array()
ans=0
for i in range(2**n):
	tmp=[]
	ans_tmp=0
	for j in range(n):
		tmp.append(i>>j&1)
	for c in range(m): # スイッチのチェック
		sw=s[c]
		sum_sw=0
		for l in sw:
			if tmp[l-1]==1:
				sum_sw+=1
		if sum_sw%2==p[c]:
			ans_tmp+=1
	if ans_tmp==m:
		ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k, s = [[] for _ in range(2)]
for _ in range(M):
    kk, *connected_switches = map(int, input().split())
    k.append(kk)
    s.append(connected_switches)

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

OFF = 0
ON = 1

ans = 0
for i in range(2 ** N):
    ptn = [OFF] * N
    for j in range(N):
        if (i >> j) & 1:
            ptn[len(ptn) - j - 1] = ON

    ON_SW_COUNT_LIST = []  # 各電球に繋がったON状態のスイッチの数リスト
    for connected_switches in s:
        on_sw_cnt = len([1 for sw in connected_switches if ptn[sw - 1] == ON])
        ON_SW_COUNT_LIST.append(on_sw_cnt)

    ans += all([c % 2 == p[i] for i, c in enumerate(ON_SW_COUNT_LIST)])

print(ans)

Submission status: Accepted

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


ls = [0]*n
param_list = [0]*2**n
for i in range(2**n):
    l = [False]*n
    for id_r, row in enumerate(ls):
        if i & (2 ** id_r) >0:
            l[id_r] = True
    param_list[i] = l 

count = 0    

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



for param in param_list:
    for i in range(m):
        tr_num = 0
        for a in range(1,k_list[i][0]+1):
            if param[k_list[i][a]-1]:
                tr_num +=1
            else:
                continue
        if tr_num % 2 is ps[i]:
            if i == m-1:
                count +=1
                
            else:
                continue
        else:
            break

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ks=[]
for i in range(m):
    temp=list(map(int,input().split()))
    ks.append(temp)
p=list(map(int,input().split()))
cnt_ans=0
for i in range(1<<n):
    cnt_on=0
    for j in range(0,m):
        cnt=0
        for k in range(1,ks[j][0]+1):
            if (i>>(ks[j][k]-1))%2==1:
                cnt+=1
        if cnt%2==p[j]:
            cnt_on+=1
    if cnt_on==m:
        cnt_ans+=1
print(cnt_ans)

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

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

    for i in range(1<<n):
        ok = True
        for j in range(m):
            cnt = 0
            for s in S[j]:
                if ((i>>s-1)&1): # スイッチが対象であれば
                    cnt += 1
            if cnt%2!=p[j]:
                ok = False
        if ok:
            ans += 1
    print(ans)




if __name__=="__main__":
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(m):
        cnt = 0
        for k in range(1, len(ks[j])):
            if (i >> (ks[j][k]-1)) & 1:
                cnt += 1
        if cnt % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

def allCombination(n):
    switch = [i for i in range(1,n+1)] 
    slis = []
    for i in range(0,n+1):
        for pair in itertools.combinations(switch, i):
            slis.append(pair)
    return slis

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

slis = allCombination(n)

cnt = 0
for s in slis:
    flag = 1
    for i,eachs in enumerate(kS):
        same = set(eachs[1:]) & set(s)
        if len(same) % 2 != p[i]:
            flag = 0
    
    if flag:
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans = 0

for i in range(2**N):
  clear_flag = 1
  for j in range(M):
    tmp = 0
    for k in ks[j]:
      k -= 1
      if (i>>k) & 1:
        tmp += 1
    if tmp % 2 != p[j]:
      clear_flag = 0
      break
  if clear_flag == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
SW = []
for _ in range(M):
    k, *s = map(int, input().split())
    SW.append([*s])
p = list(map(int, input().split()))

Onoffs = product([0, 1], repeat=N)

cnt = 0
for onoff in Onoffs:
    for i, sw in enumerate(SW):
        tmp = 0
        for j in sw:
            if onoff[j-1]:
                tmp += 1
        if tmp % 2 != p[i]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans = 0
for ii in range(2**N):
    check = True
    for i in range(M):
        cnt = 0
        for j in range(1, len(ks[i])):
            if (ii >> (ks[i][j]-1)) & 1:
                cnt += 1
        if cnt % 2 != p[i]:
            check = False
            break
    if check:
        ans += 1
print(ans)

Submission status: Accepted

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

klist = []
slist = [list() for _ in range(m)]

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

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

ans = 0
for i in range(2**n):
    for j in range(m):
        cnt = 0
        for l in slist[j]:
            if (i >> (l-1))&1 ==1:
                cnt += 1
        if cnt%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

P=list(map(int,input().split()))
for i in range(2**N):
  i=format(i,'b').rjust(N,'0')
  on=[]
  for j in range(N):
    if i[j]=='1':
      on.append(j+1)


  count2=0
    
  for k in range(M):
    count=0
    for l in Look[k]:
      if l in on:
        count+=1
    if count%2==P[k]:
       count2+=1

  if count2==M:
    ans+=1
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def countBit( n ):
    c=0
    while 1:
        c += n&1
        if n<=0:
            return c
        n //= 2


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

S=[0]*m
for i in range(m):
    K = list(map(int,input().split()))
    for j in range(1,len(K)):
        S[i]+=1<<(K[j]-1)

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

ac=0
for i in range(2**n):
    c=0
    for j in range(m):
        if countBit(S[j]&i)%2==0 and P[j]==0:
            c+=1
        elif countBit(S[j]&i)%2==1 and P[j]==1:
            c+=1
        else:
            break

    if c==m :
        # print(bin(i),bin(S[j]),i,c)
        ac+=1
print(ac)

Submission status: Accepted

Solution code:
import math
import itertools

n, m = map(int, input().split(" "))
sL = []
for i in range(m):
    _, *s = map(int, input().split(" "))
    sL.append(s)
pL = list(map(int, input().split(" ")))

bz = list(itertools.product([0, 1], repeat=n))
ans = 0
for b1 in bz:
    for i in range(m):
        s = sL[i]
        p = pL[i]
        cnt = 0
        for si in s:
            if b1[si - 1] == 1:
                cnt += 1
        if cnt % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    KS = [NLI() for _ in range(M)]
    P = NLI()
    
    ans = 0
    
    for m in range(M):
        for x in range(1,len(KS[m])):
            KS[m][x] -= 1

    bit_len = N
    for i in range(2**bit_len):
        switch = [0 for _ in range(bit_len)]
        for j in range(bit_len):
            if (i >> j) & 1:
                switch[j] = 1
        
        light = [0 for _ in range(M)]
        
        for m in range(M):
            cnt = 0
            for y in KS[m][1:]:
                if switch[y] == 1:
                    cnt += 1
            if cnt % 2 == P[m]:
                light[m] = 1
        
        if light.count(1) == M:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    s=[]
    for i in range(M):
        L=LI()
        s.append(L[1:])
    p=LI()
    
    import itertools
    
    ans=0
    for ite in itertools.product([0,1], repeat=N):
        flag=1
        for i in range(M):
            temp=0
            for ss in s[i]:
                if ite[ss-1]:
                    temp+=1
            if temp%2==p[i]:
                pass
            else:
                flag=0
        if flag:
            ans+=1
            
    print(ans)
                
                
            
        

main()

Submission status: Accepted

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

switch = [[] for _ in range(m)]

for i in range(m):
    ks = list(map(int, input().split()))
    switch[i] = ks[1:]


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

ans = 0
#print(switch)

for i in range(2 ** n):
    flag = [False] * n
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            flag[j] = True

    #print(flag)
    f = True    
    for k in range(m):
        c = 0
        for j in switch[k]:
            if flag[j-1]:
                c += 1
        if c % 2 != p[k]:
            f = False
            break
        
    if f:
            ans += 1

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
light = []
for i in range(m):
    tmp = list(map(int, input().split()))
    light.append(tmp[1:])
p = list(map(int, input().split()))
ans = 0
# 0 off, 1 on, bit全探索
for mask in range(1 << n):
    # print(mask)
    out = False
    # それぞれの電球について見る
    for i in range(len(light)):
        cnt = 0
        # 各電球が点くかを見たい
        for check in light[i]:
            if mask >> (check - 1) & 1:
                cnt += 1
        if cnt % 2 != p[i]:
            out = True
            break
    if not out:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lamp = []
for _ in range(M):
    lamp.append(list(map(int, input().split()))[1:])
P = list(map(int, input().split()))
res = 0
for bit in range(1<<N):
    on = 0
    for l in range(M):
        temp = 0
        for i in lamp[l]:
            i -= 1
            if (bit >> i) & 1 == 1:
                temp += 1
        if temp%2 == P[l]:
            on += 1
    if on == M:
        res += 1
print(res)

Submission status: Accepted

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

P = list(map(int,input().split()))
ans = 0
for num in range(1<<N):
    Light = [0] * N
    count = 0
    for i in range(N):
        bit = num>>i & 1
        if bit:
            Light[i] = 1
    for i,s in enumerate(S):
        light_count = 0
        p = P[i]
        for si in s:
            if Light[si-1]:
                light_count += 1
        if light_count % 2 == p:
            count+=1
    if count == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

cnt = 0
for pat in product([0, 1], repeat=n):
    for ksi, pi in zip(ks, p):
        tmp = sum(pat[sij - 1] for sij in ksi[1:])
        if  tmp % 2 != pi:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

cnt = 0
for pat in product([0, 1], repeat=n):
    for ksi, pi in zip(ks, p):
        tmp = sum(pat[ksij - 1] for ksij in ksi[1:])
        if  tmp % 2 != pi:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

cnt = 0
for pat in product([0, 1], repeat=n):
    for i, ksi in enumerate(ks):
        tmp = sum(pat[ksi[j + 1] - 1] for j in range(ksi[0]))
        if  tmp % 2 != p[i]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

cnt = 0
for pat in product([0, 1], repeat=n):
    for i in range(m):
        tmp = sum(pat[ks[i][j + 1] - 1] for j in range(ks[i][0]))
        if  tmp % 2 != p[i]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
ans=0
for _ in range(m):
  t=list(map(int,input().split()))
  t.pop(0)
  a.append(t)
b=list(map(int,input().split()))
for i in range(2**n):
  c=[0]*m
  for j in range(n):
     if ((i>>j) & 1):
        for k in range(len(a)):
          if (j+1) in a[k]:
            c[k]+=1
  flg=0
  for j in range(m):
    if c[j]%2!=b[j]:
      flg=1
  if flg==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lamp = [0] * M 
for j in range(M):
    s = ['0'] * N 
    k, *num = map(int, input().split())    #; print(k, num)
    for x in num:
        s[x-1] ='1'
    lamp[j] = int(''.join(s[::-1]), 2)     #; print(bin(lamp[j]))

p = [int(i) for i in input().split()] 
ans = 0
for i in range(2**N):
    for j in range(M):
        if bin(i&lamp[j]).count('1') % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int,input().rstrip().split()))
k = []
s = []
for i in range(M):
    stdin = list(map(int,input().rstrip().split()))
    k.append(stdin[0])
    s.append(stdin[1:])
p = list(map(int,input().rstrip().split()))
ans = 0
for bit in range(2**N):
    od = 0
    for j in range(M):
        odd = 0
        for sw in s[j]:
            mask = 1 << (sw-1)
            if bit&mask: # 右からi番目にビットが立っているかどうか判定
                odd += 1
        if p[j] != odd%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import OrderedDict
input = sys.stdin.buffer.readline

n, m = [int(i) for i in input().split()]
links = OrderedDict()
ans = 0

for i in range(m):
    line = [int(i) for i in input().split()]
    links[i] = line[1:]

conditions = [int(i) for i in input().split()]

switchs = [0] * (n + 1)  # 0:off,1:on
states = [0] * m

for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1:
            switchs[j] = 0
        else:
            switchs[j] = 1
    for i in range(m):
        link = links[i]
        _tmp = 0
        for x in link:
            _tmp += switchs[x - 1]
        if conditions[i] == _tmp % 2:
            states[i] = 1
        else:
            states[i] = 0
    if sum(states) == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

bit=list(product(range(2),repeat=n))
ans=0
for bi in bit:
    plst=[0]*m
    for j in range(m):
        for k in range(ks[j][0]):
            plst[j]+=bi[ks[j][1+k]-1]
    
    for j in range(m):
        if plst[j]%2!=p[j]:
            break
    else:
        ans+=1
print(ans)