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:
import sys
readline = sys.stdin.readline

def main():
    N, M = map(int, readline().rstrip().split())
    S = []
    for _ in range(M):
        _, *s = map(int, readline().rstrip().split())
        S.append(set(s))
    P = list(map(int, readline().rstrip().split()))

    ans = 0
    for i in range(2**N):
        b = bin(i)[2:].zfill((N))
        b = set([i+1 for i, e in enumerate(b) if e == '1'])
        flg = True
        for j, s in enumerate(S):
            if len(s&b) % 2 != P[j]:
                flg = False
                break
        if flg:
            ans += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

def main():
    N,M=map(int,input().split())
    sw =[list(map(int, input().split())) for _ in range(M)]
    p=[int(x) for x in input().split()]
    ans=0
    
    for i in itertools.product([0,1],repeat=N):
        onof=True
        for j in range(M):
            counter=0
            for k in sw[j][1:]:
                counter+=i[k-1]
            if counter%2!=p[j]:
                onof=False
                break
        if onof:
            ans+=1
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bulbs = []
for i in range(M):
    _, *conn_switches = map(int, input().split())
    bulbs.append(conn_switches)
P = list(map(int, input().split()))

ans = 0
for i in range(1 << N):
    on_cnt = [0] * M
    for j, conn_switches in enumerate(bulbs):
        if P[j] ^ sum(i >> s - 1 & 1 for s in conn_switches) & 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

# 解答（@maspy）

# switchが10個以下
N,M = map(int,input().split())
sw = [[] for _ in range(M)]
# print(sw) # [[], [], ..., []]

for i in range(M):
    sw[i] = list(map(int,input().split()[1:]))
# print(sw) # [[１行目], [２行目], ..., [M行目]]

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

answer = 0
for tpl in itertools.product([0,1],repeat=N):
  bl = True
  for i in range(M):
    # 電球iを計算
    s = sum([tpl[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    answer += 1
print(answer)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    on_cnt = [0] * M
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                if j + 1 in bulbs[k][1]:
                    on_cnt[k] ^= 1
    if on_cnt == p:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    on_cnt = [0] * M
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                if j + 1 in bulbs[k][1]:
                    on_cnt[k] = (on_cnt[k] + 1) % 2
    if on_cnt == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m= map(int, input().split())
    inlis = []
    swlis = []
    light = 0
    ans = 0

    for _ in range(m):
        inlis.append(list(map(int, input().split())))
    swlis = list(map(int, input().split()))
    #print(inlis)
    #print(swlis)
    for i in range(2 ** n):
        tmp = []
        for j in range(n):
            if ((i >> j) & 1):
                tmp.append("On")
            else:
                tmp.append("Off")
        for k in range (m):
            cnt = 0
            for l in range(1, len(inlis[k])):
                #print(k, l, inlis[k], inlis[k][l])
                if tmp[inlis[k][l]-1] == "On":
                    cnt += 1
            if cnt % 2 == swlis[k]:
                light += 1
                #print(k, l, tmp, swlis[k])
        if light == m:
            ans += 1
        light = 0
    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()))

res1=0
for i in range(2**n):
	res2=0
	for j in range(m):
		cnt=0
		for s in range(ks[j][0]):
			if (i>>(ks[j][s+1]-1))&1:
				cnt+=1
		if cnt%2==p[j]:
			res2+=1
	if res2==m:
		res1+=1

print(res1)

Submission status: Accepted

Solution code:
def main():
    # 入力
    n, m = map(int, input().split())
    ls = []
    for i in range(m):
        ls.append(list(map(int, input().split())))
    pls = list(map(int, input().split()))



    boolls = [[]]
    for i in range(n):
        tmpls = []
        for x in boolls:
            y = x.copy()
            x.append(True)
            y.append(False)
            tmpls.append(x)
            tmpls.append(y)
        boolls = tmpls

    cnt = 0
    for z in boolls:
        on = True
        for i in range(len(ls)):
            li = ls[i]
            pi = pls[i]

            lix = li[1:]

            oncnt = 0
            for ix in lix:
                if z[ix-1]:
                    oncnt += 1

            if oncnt % 2 != pi:
                on = False
                break
        if on:
            cnt += 1

    print(cnt)



main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = [[0] for i in range(M)]
adjacent = [[0]*N for i in range(M)]
for i in range(M):
    A = list(input().split())
    K[i] = A[0]
    for j in A[1:]:
        adjacent[i][int(j)-1] = 1
P = list(input().split())
X = 0
for i in range(2**N):
  a = 0
  b = [0]*N
  for j in range(N):
    if i%2 == 1:
      b[j] = 1
    i = i//2
  for j in range(M):
    if  sum([x*y for (x,y) in zip(b, adjacent[j])])%2 == int(P[j]):
      a += 1
  if a == M:
    X += 1
print(X)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
result = 0

for i in itertools.product([0, 1], repeat=n):
    onof = True
    for j in range(m):
        counter = 0
        for k in sw[j][1:]:
            counter += i[k-1]
        if counter % 2 != p[j]:
            onof = False
            break
    if onof:
        result += 1
print(result)

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    s=[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):
        flag=True
        for j in range(M):
            if not ([(i>>k-1)&1 for k in s[j]].count(1)%2==p[j]):
                flag=False
                
        if flag:
            ans+=1
            
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

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

num_list = list(range(N))
ans = 0
for bit in range(1<<len(num_list)):
    switch_on = []

    for i in num_list:
        mask = 1 << i
        if bit & mask:
            switch_on.append(i)
    switch_on = list(map(lambda x: x+1, switch_on))

    tmp = 0
    for i in range(len(switches)):
        on_flg = set(switches[i][1:]) & set(switch_on)
        if len(on_flg) % 2 == p[i]:
           tmp += 1
    if(tmp == M):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for i in itertools.product([0, 1], repeat=n):
    test = True
    for j in range(m):
        count = 0
        for s in k_list[j][1:]:
            count += i[s-1]
        if count % 2 != p[j]:
            test = False
            break
    if test:
        ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

for i in range(2**N):
    switch_flag=[0]*N
    for j in range(N):
        flag = 0
        switch_flag[j]=(i>>j)&1
    for k in range(M):
        total = 0
        for l in range(switch[k][0]):
            if switch_flag[switch[k][l+1]-1] == 1:
                total += 1
        if total%2 == P[k]:
            flag += 1
    if flag == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ks=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
ans=0
for s in range(1<<N):
    for j in range(M):
        cnt=0
        for h in ks[j][1:]:
            h-=1
            if (s>>h)&1:
                cnt+=1
                cnt%=2
        if cnt!=p[j]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

# スイッチで全探索
bulb = []
for _ in range(M):
    enc = 0
    s = list(map(int, input().split(" ")))
    for k in range(s[0]):
        enc = enc | (1 << (s[k + 1] - 1))
    bulb.append(enc)

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

ans = 0
for s in range((1 << N)):
    count = 0
    for i, enc in enumerate(bulb):
        if bin(enc & s).count("1") % 2 == p[i]:
            count += 1
    if count == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
lamp_list = [list(map(int, input().split())) for i in range(m)]
#for i in range(m):
#  lamp_list.append(input())
p = list(map(int, input().split()))
counter = 0

for i in range(2 ** n):
  num_list = []
  for j in range(n):
    if (i >> j) & 1:
      num_list.append(j + 1)
  #print(lamp_list)
  count_flag = True
  for _index, lamp in enumerate(lamp_list):
    lamp_counter = 0
    for lamp_num in lamp[1:]:
      if lamp_num in num_list:
        lamp_counter += 1
    if lamp_counter % 2 != p[_index]:
      count_flag = False
      break
  if count_flag:
    #print(_index, lamp[1:], num_list, lamp_counter, p[_index])
    counter += 1
  #print(_index, lamp, lamp_counter, p, counter)
print(counter)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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

#print()
ans = 0
for i in range(2**n):
    on = []
    for j in range(n):
        if ((i>>j) & 1):
            on.append(j)
    #print('on:', on)
    allon = True
    for j in range(m):
        sumv = 0
        for x in s[j]:
            if (x - 1) in on:
                sumv += 1
        #print(j,':', sumv)
        if sumv%2 != p[j]:
            allon = False
            break
    if allon:
        ans += 1
#print()
print(ans)

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
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 bit in range(1 << n):
    ptn = bin(bit)[2:].rjust(n,'0')
    light = True
    for j in range(m):
        tmp = 0
        for k in range(1, s[j][0] + 1):
            if ptn[s[j][k] - 1] == '1':
                tmp += 1
        if tmp % 2 != p[j]:
            light = False
    if light:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
sbit = [0] * M
for i in range(M):
  l = list(map(int, input().split()))
  bit = 0
  for j in range(1, l[0] + 1):
    bit += 1 << (l[j] - 1)
  sbit[i] =  bit
p = list(map(int, input().split()))

total = 0
for tbit in range(2 ** N):
  flg = True
  for i in range(M):
    bit = sbit[i] & tbit
    bits = 0
    while bit > 0:
      if bit & 1:
        bits += 1
      bit = bit >> 1
    if bits % 2 != p[i]:
      flg = False
      break
  if flg:
    total += 1
print(total)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
k = [0] * M
s = [[0] for _ in range(M)]
for i in range(M):
    k[i], *s[i] = map(int, input().split())
p = list(map(int, input().split()))
a = list(product([0, 1], repeat=N))  # N=3なら000~111までの8個の直積のリスト
# print(a)

ans = 0
for c in a:  # スイッチ状態を全てについて調べる
    cnt = 0
    for i in range(M):  # 電球はM個ある
        tmp = 0
        for t in s[i]:  # s[i]には電球iのスイッチ条件
            tmp += c[t - 1]  # s[i]に書かれていたスイッチのOn／offをtmpに足していく．
            # print("tmp : {}".format(tmp))
        if tmp % 2 == p[i]:
            cnt += 1
    if cnt == M:  # 全ての電球が点灯するなら，組み合わせ数に一つ加える
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

for i in range(2**n): #onになっているswの組み合わせ
    for sw, p in zip(swl, pl):
        odd = False
        for a in sw:
            if i & 1 << (a - 1): #今見ている電球と連動しているswがonかどうか
                odd = not odd
        if int(odd) != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

lights = []
for i in range(m):
    lights.append([int(_) for _ in input().split(' ')[1:]])

rules = [int(_) for _ in input().split(' ')]

patterns = []
for i in range(2**n):
    tmp = ['off'] * n
    for j in range(n):
        if (i >> j & 1):
            tmp[j] = 'on'
    patterns.append(tmp)

count = 0
for p in patterns:
    bright = 0
    for i in range(m):
        on_count = 0
        for switch in lights[i]:
            if(p[switch-1] == 'on'):
                on_count += 1
        if(on_count%2 == rules[i]):
            bright += 1
    if(bright == m):
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
def get_switch(i, N):
    ans = list()
    for _ in range(N):
        ans.append(i%2)
        i //= 2
    return ans

def turn_light(switch, k_s, p, N, M):
    for i in range(M):
        count = 0
        for j in range(1, k_s[i][0]+1):
            if switch[k_s[i][j]-1] == 1:
                count += 1
        
        if count % 2 != p[i]:
            return 0
    
    return 1

N, M = map(int, input().split())
k_s = list()
for i in range(M):
    k_s.append(list(map(int, input().split())))

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

ans = 0
for i in range(2**N):
    switch = get_switch(i, N)
    ans += turn_light(switch, k_s, p, N, M)

print(ans)

Submission status: Accepted

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

count = 0
for i in range(2 ** N):
    bin_str = format(i, 'b')
    if len(bin_str) < N:
        bin_str = '0' * (N - len(bin_str)) + bin_str
    bool = True
    for j in range(M):
        switch_count = 0
        for S in s[j]:
            if int(bin_str[S - 1]) == 1:
                switch_count += 1
        if switch_count % 2 != p[j]:
            bool = False
            break
    if bool:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
k = []
for i in range(m):
    ipt = list(map(int, input().split()))
    k.append(ipt[0])
    s.append(ipt[1:])
p = list(map(int, input().split()))
cnt = 0
for sw in (list(format(i, '0{}b'.format(n))) for i in range(2 ** n)):
    for i in range(m):
        if sum([int(sw[j - 1]) for j in s[i]]) % 2 != p[i]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

N,M=map(int,input().split())
k=[0]*M
s=[[0] for _ in range(M)]
for i in range(M):
  k[i],*s[i]= map(int,input().split())
p= list(map(int,input().split()))
a=list(product([0,1],repeat=N))

ans=0
for c in a:  #スイッチ状態
  cnt=0
  for i in range(M):  #電球はM個ある
    tmp=0
    for t in s[i]:
      tmp += c[t-1]
    if tmp%2==p[i]:
      cnt +=1
  if cnt==M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    n, m = MI()
    switch = [0 for _ in range(n)]
    for i in range(m):
        l = LI1()
        k = l[0]
        s = l[1:]
        # print(k, s)
        for ss in s:
            switch[ss] = switch[ss] | (1 << i)

    # print(switch)
    P = 0
    for j, l in enumerate(LI()):
        P = P | (l << j)
    # print(P)

    ans = 0
    for i in range(pow(2, n)):
        x = 0
        # print(bin(i))
        for j in range(n):
            # print('  ', j)
            if 1 & (i >> j):
                # print('    Y', x, switch[j])
                x = x ^ switch[j]
                # print(x)
        if x == P:
            ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

num_cases = 0

for i in range(2 ** n):
    flag = 0
    num_on_e = 0
    for j, k in zip(elec, p):
        if flag:
            break
        else:
            switches = j[1:]
            num_on_switch = 0
            for s in switches:
                if i & (1 << s - 1):
                    num_on_switch += 1

            if num_on_switch % 2 == k:
                num_on_e += 1
            else:
                flag = 1
    if num_on_e == m:
        num_cases += 1
print(num_cases)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    n,m = na()#swich,light
    ks = []
    swicthToLight = [[] for _ in range(n)]
    for i in range(m):
        ss = na()
        k = ss.pop(0)
        ks += [k]
        for s in ss:
            swicthToLight[s-1] += [i]
    ps = na()
    ans = 0
    for i in range(pow(2,n)):
        pstmp = [i for i in ps]
        for j in range(n):
            if ((i>>j) & 1):
                for light in swicthToLight[j]:
                    pstmp[light] += 1
                    pstmp[light] %= 2
        if sum(pstmp) == 0:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().rstrip().split(" "))
K = [[]] * M
sw = [False] * N
count = 0
check = True
ans = 0

for i in range(M):
    K[i] = list(map(int,input().rstrip().split(" ")))
P = list(map(int,input().rstrip().split(" ")))


for i in range(2 ** N):
    check = True
    for i2 in range(N):
        sw[i2] = (i >> i2) & 1
    
    for i2 in range(M):
        counter = 0
        for i3 in range(K[i2][0]):
            if sw[K[i2][i3 + 1] - 1]:
                counter += 1
        if counter % 2 != P[i2]:
            check = False
            break
    if check: 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)]
t=list(map(int,input().split()))
ans=0
for i in range(2**n):
  bit=[i>>j & 1 for j in range(n)]
  for k,x in enumerate(s):
    if t[k]!=sum([bit[y-1] for y in x[1:]])%2:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    ans = [0] * m

    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1): #ついてるのが1
            for k in range(m):
                if j+1 in ks[k][1:]:
                    ans[k] += 1
    flag = True
    for j in range(m):
        if ans[j] % 2 != p[j]:
            flag = False
            break
    if flag:
        aans += 1
print(aans)

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):
    bit = [i>>j & 1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for j in range(2**N):
    n = 0  
    for m in range(M):
        t = 0
        for sw in l[m]:
            if (j>>(sw-1)&1):
                t += 1
        if t%2 == p[m]:
            n += 1
        else:
            break
    if n == M:
        ans += 1
print(ans)

Submission status: Accepted

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

count = 0
for i in range(2 ** n):
    on_light = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in switch[k]:
                    on_light[k] += 1
    if all((on_light[i] % 2 == p[i]) for i in range(m)):
        count += 1

print(count)

Submission status: Accepted

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

s = [list(map(int, input().split())) for _ in range(m)]
k = [0] * m
for i in range(m):
    k[i] = s[i][0]
    del s[i][0]
p = list(map(int,input().split()))
ans = 0
for b in range(2 ** n):
    sum = 0
    cnt = [0] * m 
    flag = [False] * m
    for j in range(n):
        if b >> j & 1:
            for k in range(m):
                if (j + 1) in s[k]:
                    cnt[k] += 1
    #print(cnt, b)
    for i in range(m):
        if cnt[i] % 2 == p[i]:
            flag[i] = True
    
    if all(flag[i] == True for i in range(m)):
        """
        print(b)
        print(flag)
        """
        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()))

ans=0

for i in range(2**N):
    swi=bin(i)[2:].rjust(N, "0")
    lights=1

    for j in range(M):
        cnt=0
        for k in range(1, s[j][0]+1):
            if swi[s[j][k] -1] == "1":
                cnt+=1

        if cnt%2 != p[j]:
            lights=0
    
    if lights==1:
        ans+=1

print(ans)

Submission status: Accepted

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

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

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

ans = 0

for i in range(2**n): #電源on/offの全パターン
    for sw, p in zip(l, pl):
        odd = False
        for a in sw:
            if i & 1 << (a - 1): #onになっているswと連動しているか
                odd = not odd #True/Falseを切り替えている。
        if int(odd) != p: #Trueは1, Falseは0になる。
            break
    else: #breakでループを抜けなかった時だけ実行される
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [[] for _ in range(m)]
for i in range(m):
    temp = list(map(int,input().split()))
    s[i] = temp[1:]#電球がどのスイッチと接続されているかの情報が詰まっています。
p = list(map(int,input().split()))
ans = 0

for i in range(2**n):#スイッチの入れ方を列挙します。
    switches_on = [0 for _ in range(m)]#電球の点灯に関係するスイッチが何個onになっているかを確認します。
    for j in range(n):
        if (i >> j) & 1:#j+1の番号を持ったスイッチはonになっています。
            for k in range(m):
                if j+1 in s[k]:
                    switches_on[k] += 1
    light_on = [0 for _ in range(m)]
    for j in range(m):
        if (switches_on[j]%2) != (p[j]%2):#j番の電球が点灯しなかった場合
            light_on[j] = False
        else:#i番の電球が点灯する場合
            light_on[j] = True
    if all(light_on):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# https://atcoder.jp/contests/abc128/tasks/abc128_c

def solve():
    N, M = list(map(int, input().split()))
    denkyu = []
    for i in range(M):
        inputs = list(map(int, input().split()))
        k, Ss = inputs[0], inputs[1:]
        denkyu.append(Ss)
    Ps = list(map(int, input().split()))

    # スイッチの状態をbit全探索
    ans = 0
    for bits in range(2**N): # 1024
        light = 0  # 点灯している数
        for j in range(M): # 10
            total = 0
            for sw in denkyu[j]: # 10
                if (bits>>(sw-1)&1):
                    total += 1
            if total%2 == Ps[j]:
                light += 1
            else:
                break
        if light == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switch = list()
for i in range(M): 
  x = list(map(int, input().split()))
  switch.append(x[1:])
mod = list(map(int, input().split()))

ans = 0
for n in range(2**N):
  flag = 1
  useswitch = list()
  cnt = [0] * M
  for i in range(N):
    if n>>i & 1 == 1:
      useswitch.append(i+1)
      
  for m in range(M):
    for s in useswitch:
      if s in switch[m]:
        cnt[m] = (cnt[m]+1)%2
        
  
  for i in range(M):
    if(cnt[i] != mod[i]):
      flag = 0
      
  if(flag == 1):
    ans += 1
  
    
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    s=[]
    for i in range(m):
        ss=[int(_) for _ in input().split()]
        s.append(ss[1:])
    P=[int(_) for _ in input().split()]
    ans=0
    for j in range(2**n):
        i=0#i桁目が1ならi番目を使う
        nn=j#nn=1010110
        Q=[0]*m #onになってる数
        while nn>0:
            if ((nn&1)==1):
                for x,ss in enumerate(s):
                    if i+1 in ss:
                        Q[x]+=1
            nn>>=1
            i+=1
        for x,q in enumerate(Q):
            if q%2!=P[x]:
                break
        else:
            ans+=1
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]

light_list = [0] * m
for i in range(m):
    temp = [int(x) for x in input().split()]
    light = 0
    for j in range(1, temp[0] + 1):
        light |= 1 << (temp[j] - 1)
    light_list[i] = light

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555)
    x = (x & 0x3333) + ((x >> 2) & 0x3333)
    x = (x + (x >> 4)) & 0x0f0f
    x = x + (x >> 8)
    return x & 0xf

ans = 0
for i in range(2 ** n):
    temp = 0
    for j in range(m):
        if popcount(i & light_list[j]) % 2 != p_list[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
cin = open(0).read().split('\n')

n, m = map(int, cin[0].split(' '))
s = []
for row in cin[1:1+m]:
    s.append(list(map(int, row.split(' ')[1:])))
p = list(map(int, cin[1+m].split(' ')))

ret = 0
for ai in range(2**n):
    flg = True
    for idx, si in enumerate(s):
        on_cnt = 0
        for sii in si:
            if (ai >> (sii-1)) & 1:
                on_cnt += 1
        if on_cnt % 2 != p[idx]:
            flg = False
    if flg:
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# N:スイッチの数、M：電球の数
s = [[] for _ in range(M)]
for i in range(M):
    temp = list(map(int, input().split()))
    s[i] = temp[1:]
p = list(map(int, input().split()))
ans = 0

# bit全探索
for i in range(2 ** N):
    on = [0 for _ in range(M)]
    for j in range(N): 
        if (i >> j) & 1:
            for k in range(M):
                if j+1 in s[k]:
                    on[k] += 1
    tf = []
    for on_n, p_n in zip(on, p):
        if on_n % 2 == p_n:
            tf.append(True)
        else:
            tf.append(False)
    if all(flg for flg in tf):
        ans += 1

print(ans)