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())
s=[]
count=0
for i in range(m):
    tmp=list(map(int,input().split()))
    s.append(tmp[1:])

p=list(map(int,input().split()))
p=list(map(bool,p))
p=list(map(lambda x:not x,p))

for i in range(2**n):
    tmp_p=p[:]#shallow copy
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if j+1 in s[k]:
                    tmp_p[k]^=True#toggle

    if all(tmp_p):
        count+=1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    flag = True
    for a in range(M):
        cnt = 0
        for b in lightList[a][1:]:
            if not (i & (1<<b-1)):
                cnt += 1
        if cnt % 2 != P[a]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# input
a, b = map(int, input().split())
c = []
for i in range(b):
    c.append(list(map(int, input().split())))
p = list(map(int, input().split()))
out = 0
for j in range(1 << a):
    t = format(j, 'b').zfill(a)
    o = 0
    for k in range(b):
        s = 0
        for l in range(c[k][0]):
            s += int(t[(c[k][l+1]-1)])
        if s % 2 == p[k]:
            o += 1
    if b == o:
        out += 1
print(out)

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 num in range(1<<n):
	all = True
	for M in range(m):
		swt = 0
		for k in s[M][1:]:
			if num&(1<<(k-1)):
				swt += 1
		if swt % 2 != p[M]:
			all = False
			break
	if all:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
list_Connect=[]
for i in range(M):
    A = list(map(int, input().split()))
    A.pop(0)
    list_Connect.append( A )

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

i = 0



state = []#スイッチ点灯の全組み合わせを入れる
sum=0

def func(i):
    global sum
    if i == N:
        flag = True
        for i in range(M):
            cnt= 0
            for j in list_Connect[i]:
                cnt += state[j-1]
            if cnt %2 != list_p[i]:
                flag = False
                break
        if flag == True:
           sum+=1
    else:
        state.append(1)
        func(i+1)
        state.pop(-1)
        state.append(0)
        func(i+1)
        state.pop(-1)

    return


func(0)
print (sum)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list1=[]
for i in range(M):
    list1.append(list(map(int,input().split()))[1:])
plist=list(map(int,input().split()))
ans=0
for i in range(2**N):
    listtemp=[0]*N
    for j in range(N):
        listtemp[j]=(i>>j)
    for num in range(len(list1)):
        x=0
        for y in list1[num]:
            x+=(listtemp[y-1])
        if plist[num]!=x%2:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

# 入力
N, M = map(int, input().split())
k, s = zip(
    *(
        (k, s)
        for _ in range(M)
        for k, *s in [map(int, input().split())]
    )
)
p = list(map(int, input().split()))

# 全探索で解を求める
ans = sum(
    all(
        sum(t[j - 1] for j in S) % 2 == P
        for S, P in zip(s, p)
    )
    for t in product(range(2), repeat=N)
)

# 出力
print(ans)

Submission status: Accepted

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

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

switches_pattern = []
for i in range(2**n):
    switches_pattern.append(list(map(int, format(i, "b").zfill(n))))

result = 0
for pattern in switches_pattern:
    light_bulb = True
    for i in range(m):
        bulb_count = 0
        for bulb_index in switches[i][1:]:
            if pattern[bulb_index - 1] == 1:
                bulb_count += 1
        if bulb_count % 2 != p[i]:
            light_bulb = False
        
    if light_bulb:
        result += 1

print(result)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
k = []
s = [[] for _ in range(M)]

switch = [0] * N
ans = 0

#k, sの入力
for i in range(M):
	tmp = list(map(int, input().split()))
	k.append(tmp[0])
	for j in tmp[1:]:
		s[i].append(j)

#pの入力
p = list(map(int, input().split()))

for i in range(2 ** N):#全パターン総当たり
	tmp2 = i
	for j in range(N):#ONしてるスイッチを2進数で表示
		switch[j] = tmp2 % 2
		tmp2 = int(math.floor(tmp2 / 2))
		
	count2 = 0
	for j in range(M):#M個の電球を確認
		count1 = 0
		for k in s[j]:
			if switch[k - 1] == 1:
				count1 += 1
				
		if count1 % 2 == p[j]:
			count2 += 1
			
	if count2 == M:
		ans += 1
		
print(ans)

Submission status: Accepted

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

	for i in range(M):
		s = list(map(int, input().split()))
		S[i] = s[1:]
	P = list(map(int, input().split()))
	num = 2**N
	ans = 0
	for i in range(num):
		cur = list(P)
		for j in range(M):
			for e in S[j]:
				if (i >> e-1)&1 == 1:
					cur[j] += 1
		if all(x%2==0 for x in cur):
			ans += 1
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def resolve():
    # スイッチ数, 電球数
    (n, m) = list(map(int, input().split(" ")))
    ks = [] # 電球リスト、idx:0は対応するスイッチの個数
    for i in range(m):
        o = list(map(int, input().split(" ")))
        ks.append(o)
    ps = list(map(int, input().split(" "))) # 偶数か奇数か

    swstates = [2] * n
    cnt = 0
    for i in range(2 ** n):
        bins = format(i,'b').zfill(n)
        flg = False
        # 各電球につながったswitchについて、onの数を計算
        for j, k in enumerate(ks): # k[1:]は電球につながったスイッチのリスト
            ons = 0
            for s in k[1:]: # sは電球につながったスイッチ
                ons += int(bins[s-1])
            # 電球kにつながるswitchのonの数がわかった
            # 電球kにつながるswitchオンのodd/evenがps[j]と一致する必要がある
            if not ps[j] == ons % 2:
                flg = False
                break
            else:
                flg = True
        if flg:
            cnt += 1
    print(cnt)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

ans = 0
for b in range(1<<N):
    for i in range(M):
        c = 0
        for s in src[i][1:]:
            if b&(1<<(s-1)):
                c += 1
        if c%2 != P[i]: break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

def check(status, switches, p):
    cnt = 0
    for s in status:
        if s in switches:
            cnt += 1
    return cnt % 2 == p

total = 0
for status in range(2**n):
    on = []
    for i in range(n):
        if status & 2**i:
            on.append(i+1)
    all_light = True
    for i in range(m):
        if not check(on, lights[i], ps[i]):
            all_light = False
            break
    if all_light:
        total += 1
print(total)

Submission status: Accepted

Solution code:
def sum(A):
    a=0
    for num in range(len(A)):
        a=a+A[num]
    return a
             


N,M=input().split()
N=int(N)
M=int(M)
K=[100]*(M+1)
for num in range(M+1):
    K[num]=input().split()
    for num2 in range(len(K[num])):
        K[num][num2]=int(K[num][num2])

a=[0]*N
cnt=0
for num in range(pow(2,N)):
    flag=0
    n=num
    i=0
    while(N>i):
        a[N-1-i]=n//pow(2,N-1-i)
        if(a[N-1-i]==1):
            n=n-pow(2,N-1-i)
        i=i+1
    for num2 in range(M):
        b=0
        for num3 in range(len(K[num2])-1):
            b=b+a[K[num2][num3+1]-1]
        if(b%2!=K[M][num2]):
            flag=1
    if(flag==0):
        cnt=cnt+1
print(cnt)

Submission status: Accepted

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

for i in range(2 ** n):
    on_off = [0] * n
    for j in range(n):
        if i >> j & 1:
            on_off[j] = 1
    
    for j in range(m):
        cnt = 0
        
        for k in bulbs[j][1:]:
            cnt += on_off[k - 1]
        
        if cnt % 2 != p[j]:
            cmb[i] = 0
            
print(sum(cmb))

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

num = 2 ** N
result = 0

for i in range(num):
    flag = True
    pattern = bin(i)[2:]
    pattern = '0' * (N-len(pattern)) + pattern

    for j in range(M):
        sw = 0
        for k in range(ks[j][0]):
            if pattern[ks[j][k+1]-1] == '1':
                sw += 1

        if sw % 2 != p[j]:
            flag = False
            break

    if flag:
        result += 1

print(result)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mask = [0]*m
ans = 0
#maskbitとして使う
for i in range(m):
  for j in [int(w) for w in input().split()][1:]:
    mask[i] += (1 << j-1)
p = [1 ^ int(i) for i in input().split()]
#maskbitと論理積を取ってからpとxorで判定
for i in range(1 << n):
  cnt = 0
  for j in range(m):
    temp = i & mask[j]
    flag = p[j]
    for k in range(n):
      flag ^= (temp >> k) & 1
    if flag:
      cnt += 1
  if cnt == m:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks_array = [[int(x) for x in input().split()] for y in range(m)]
p_array = [int(x) for x in input().split()]
k_array = [x[0] for x in ks_array]
s_array = [x[1:] for x in ks_array]

comb = 2 ** n
cnt = 0
for i in range(comb):
    now = [False for x in range(n)]
    bit = bin(i)
    for index in range(n):
        if bin(i >> index)[-1] == "1":
            now[index] = True

    flag = True
    for index, ss in enumerate(s_array):
        tmp = 0
        for s in ss:
            if now[s-1]:
                tmp += 1
        if tmp % 2 != p_array[index]:
            flag = False
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import copy

n, m = map(int, input().split())
ks_ls = []
count = 0
while count < m:
    ks_ls.append(list(map(int, input().split())))
    count = count + 1
p_ls = list(map(int, input().split()))

all_pattern = []
hoge = [0]
hoge2 = [1]
all_pattern.append(hoge)
all_pattern.append(hoge2)
count2 = 0
while count2 < n-1:
    temp = []
    for s in all_pattern:
        hoge3 = s
        hoge4 = copy.deepcopy(s)
        hoge3.append(0)
        hoge4.append(1)
        temp.append(hoge3)
        temp.append(hoge4)
    count2 = count2 + 1
    all_pattern = temp
result = []
for i in all_pattern:
    ok_flg = True
    for index2, j in enumerate(ks_ls):
        sum = 0
        for index, k in enumerate(j):
            if index == 0:
              continue
            sum = sum + i[k-1]
        if sum%2 != p_ls[index2]:
            ok_flg = False
    if ok_flg :
        result.append(i)
print(len(result))

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
masks = [0] * n
for i in range(m):
    _, *ss = map(int, input().split())
    for s in ss:
        masks[s - 1] |= 1 << i
init = int(''.join(input().strip().split())[::-1], base=2)

def gray(n):
    if n == 1:
        yield 0
    else:
        yield from gray(n-1)
        yield n - 1
        yield from gray(n-1)

v = init
cnt = int(not v)
for i in gray(n):
    v ^= masks[i]
    if not v:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = []
for mi in range(m):
  tmp = list(map(int,input().split()))[1:]
  lli = [0]*n
  for ni in range(n):
    if (ni+1) in tmp:
      lli[ni] = 1
  li += [lli]
p = list(map(int,input().split()))
yyy = [0]*n
score = 0
while True:
  must1 = 1
  for mi in range(m):
    onoff = 0
    for ni in range(n):
      onoff += li[mi][ni]*yyy[ni]
    should1 = bool(onoff%2 == p[mi])
    must1 *= should1
  if must1 == 1:
    score += 1
  yyy[0] += 1
  for ni in range(n-1):
    if yyy[ni] == 2:
      yyy[ni] = 0
      yyy[ni+1] += 1
  if yyy[n-1] == 2:
    break
print(score)

Submission status: Accepted

Solution code:


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

masks = []
for i in range(M):
    x = input().split()
    k = int(x[0])
    s = x[1:]
    m = 0
    for b in s:
        m += 2**(int(b)-1)
    masks.append(m)

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

# print(masks)
# print(p)

# N, M = 2, 2
# masks = [3, 2]
# p = [0, 1]

# N, M = 2, 3
# masks = [3, 1, 2]
# p = [0, 0, 1]

# N, M = 5, 2
# masks = [19, 6]
# p = [1, 0]

combinations = 0
for b in range(2**N):
    all_on = True
    for m, c in zip(masks, p):
        if bin(b&m).count("1")%2 != c:
            all_on = False
            break
    if all_on:
        combinations += 1

print(combinations)

Submission status: Accepted

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

all_on = 0
for sp in product([0, 1], repeat=n):
    on = 0
    # 対象の電球を固定
    for i in range(m):
        cnt = 0
        # スイッチを固定
        for j in range(len(s[i])):
            if sp[s[i][j] - 1] == 1:
                cnt += 1
        if cnt % 2 == p[i]:
            on += 1
    if on == m:
        all_on += 1

print(all_on)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
list1 = []
for i in range(M):
  Input = input().split()
  k = int(Input[0])
  list1.append([])
  for j in range(k):
    list1[i].append(int(Input[j + 1]))
p = list(map(int, input().split()))
sum = 0
sumsum = 0
Bool = True
for l in range(2 ** N):
  onoff = format(l, 'b')
  onoff = onoff.zfill(N)
  for m in range(M):
    for n in range(len(list1[m])):
      sum += int(onoff[list1[m][n] - 1])
    if (not sum % 2 == p[m]):
      Bool = False
    sum = 0
  if Bool:
    sumsum +=1
  Bool = True
print(sumsum)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    S = set([1+j for j in range(N) if 2**j & i])
    for j, k in enumerate(K):
        if len(S.intersection(k))%2 != P[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

def main():
    n,m = map(int, input().split()) # n represents switch, m represents lights
    lights=[]
    for i in range(m):
        ll=list(map(int, input().split()))
        lights.append(ll[1:])
    p = list(map(int, input().split()))
    # eprint(lights)
    # eprint(s)
    ans=0
    for case in range((1<<n)):
        # eprint(bin(case))
        # cnt_switch_on = 0
        ii=0
        f_flag=0
        for light in lights:
            cnt_on=0
            for i in light:
                if (case>>(i-1))&1:
                    cnt_on+=1
            # eprint(cnt_on,p[ii])
            if  cnt_on%2!=p[ii]:
                f_flag=1
            ii+=1
        if f_flag==0:
            ans+=1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

# import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd
# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq


# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# # from itertools import accumulate
# # from collections import deque
# import random


def main():
    n,m = map(int, input().split()) # n represents switch, m represents lights
    lights=[]
    for i in range(m):
        ll=list(map(int, input().split()))
        lights.append(ll[1:])
    p = list(map(int, input().split()))
    eprint(lights)
    # eprint(s)
    # l=s
    # l[1]=[]
    # eprint(l,s)
    
    # cnt_ans=0
    ans=0
    for case in range((1<<n)):
        eprint(bin(case))
        # cnt_switch_on = 0
        ii=0
        f_flag=0
        for light in lights:
            cnt_on=0
            for i in light:
                if (case>>(i-1))&1:
                    cnt_on+=1
            eprint(cnt_on,p[ii])
            if  cnt_on%2!=p[ii]:
                f_flag=1
            ii+=1
        if f_flag==0:
            ans+=1
    print(ans)

        
    #     for i in range(n):
    #         if (case>>i)&1:
    #             cnt_switch_on +=1
    #             eprint("cnt_switch_on",cnt_switch_on)
    #     f_flag=0
    #     for light in range(m):
    #         if cnt_switch_on % 2 == p[light]:
    #             eprint("剰余",cnt_switch_on % 2,"p",p[light])
    #         else:
    #             f_flag=1
    #     if f_flag==0:
    #         cnt_ans+=1
    #     eprint("cnt_ans",cnt_ans)
    
    # print(cnt_ans)


    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
bulbs = [] * M
for i in range(M):
    bulb = list(map(int, input().split()))
    del bulb[0]
    bulbs.append(bulb)
p = list(map(int, input().split()))
seqs = list(itertools.product((0, 1), repeat=N))
for i_bulbs in range(len(bulbs)):
    target = []
    for i_seqs in range(len(seqs)):
        count = 0
        for num in bulbs[i_bulbs]:
            count += seqs[i_seqs][num - 1]
        if count % 2 != p[i_bulbs]:
            target.append(i_seqs)
    for i in reversed(target):
        del seqs[i]
    if not len(seqs):
        break
print(len(seqs))

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    bin_i = str(bin(i))[2:].zfill(N)
    flag = True
    for m in range(M):
        mm = 0
        for n in range(len(s[m])):
            if bin_i[s[m][n]-1] == '1':
                mm += 1
        if mm % 2 == p[m]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1
        
print(ans)

Submission status: Accepted

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

s_array = [x[1:] for x in array]
k_array = [x[0] for x in array]

res = 0
bit = 2 ** n
for bit_tmp in range(bit):
    flags = [False for x in range(n)]
    light_flag = True
    for shift in range(n):
        if 1 & bit_tmp >> shift:
            flags[shift] = True
    for index, s in enumerate(s_array):
        tmp = 0
        for ss in s:
            if flags[ss - 1]:
                tmp += 1
        if tmp % 2 != p_array[index]:
            light_flag = False
    if light_flag:
        res += 1
print(res)

Submission status: Accepted

Solution code:
# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy

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


# 各スイッチがどの電球につながっているかの情報をビットで保持する配列
# 1番目のスイッチが2番目と3番目の電球につながっていた場合以下のようにいなる
# (1 << 1) | (1 << 2) = (110)b   ※ zero index
mask_list = [0 for _ in range(N)]

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

    # switchesの2番目以降の要素には、スイッチの番号が入っている
    for j in range(1, len(switches)):
        sw_num = (switches[j] - 1) # スイッチの番号をzero index で管理する
        sw_bit = 1 << i # つながっている電球を二進数で表す
        mask_list[sw_num] = mask_list[sw_num] | sw_bit

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

conds_dec = 0

for i in range(len(conds)):
    conds_dec |= conds[i] << i

light_num = 0
for s in range(1 << N):
    t = 0
    for i in range(N):
        if s >> i & 1:
            t = t ^ mask_list[i]
    if t == conds_dec:
        light_num += 1


print(light_num)

Submission status: Accepted

Solution code:
# コンテスト中は無理やりなビット全探索[alias bit全探索]をしたが、正しく書き換えた

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

count = 0
for i in range(2 ** N):
    flg = True
    for m in range(M):
        on = 0
        for s in S[m]:
            if (i >> s - 1) & 1:
                on += 1
        if on % 2 != P[m]:
            flg = False
            break
    if flg:
        count += 1
print(count)

Submission status: Accepted

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

Switches = [None] + [ list([0]) for _ in range(N) ]
Ss = [list(map(lambda x: Switches[int(x)], input().split()[1:])) for _ in range(M)]
for coil, S in zip(map(int, input().split()), Ss):
    S.append([coil])

cnt = 0
for L in range(pow(2, N)):

    for i, onoff in enumerate(((L & (1 << x)) != 0 for x in range(N))):
        Switches[i+1][0] = onoff

    if sum((1 for sji in Ss if sum((1 for si in sji for siv in si if siv)) % 2 != 0 )) <= 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
count = 0
light = [0] * m
sw = [[] for _ in range(n)]

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

for pattern in itertools.product([0, 1], repeat=n):
    flag = True
    check = [0] * m
    for checkSW in range(n):
        if pattern[checkSW] == 1:
            for c in sw[checkSW]:
                check[c] += 1
    for q in range(m):
        if check[q] % 2 != p[q]:
            flag = False
    if flag:
        count += 1


print(count)

Submission status: Accepted

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

Switches = [None] + [ list([0]) for _ in range(N) ]
Ss = [list(map(lambda x: Switches[int(x)], input().split()[1:])) for _ in range(M)]
for coil, S in zip(map(int, input().split()), Ss):
    S.append([coil])

cnt = 0
for L in range(pow(2, N)):

    for i, onoff in enumerate(((L & (1 << x)) != 0 for x in range(N))):
        Switches[i+1][0] = onoff

    if sum((sum((1 for si in sji for siv in si if siv)) % 2 != 0 for sji in Ss)) <= 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = list(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(1<<n):
  good = True
  for j in range(m):
    cur = 0
    for e in s[j][1:]:
      if i&(1<<(e-1)):
        cur += 1
    if cur%2!=p[j]:
      good = False
      break
  if good:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

# 入力
N, M = map(int, input().split())
k, s = zip(
    *(
        (int(k), list(map(int, s.split())))
        for _ in range(M)
        for k, s in [input().split(maxsplit=1)]
    )
)
p = list(map(int, input().split()))

# 全探索で解を求める
ans = sum(
    all(
        sum(t[j - 1] for j in S) % 2 == P
        for S, P in zip(s, p)
    )
    for t in product(range(2), repeat=N)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=N):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import numpy as np

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

ks_list = []

for i in xrange(m):
	ks_list.append(map(int,raw_input().split()))

#print ('ks_list',ks_list)

p_list = (map(int,raw_input().split()))

cordStates = [[0 for i in range(m)] for j in range(n)]

for i in xrange(m):
    for j in xrange(ks_list[i][0]):
        tmp =  ks_list[i][j+1]-1
        cordStates[tmp][i] = 1

#print ('cordStates', cordStates)

SwStates = [[0 for i in range(n)] for j in range(2**n)]

for i in xrange(2**n):
    SwBin = format(np.left_shift(i, 0), '0'+str(n)+'b')
    SwStates[i]=list(SwBin)
    SwStates[i] = list(map(int, SwStates[i]))  

#print ('SwStates',SwStates)

LightStates = [[0 for i in range(m)]for j in range(2**n)]

#i:len(SwState) j:Swcount k:Lightcount
for i in xrange(1,(2**n)):
    nowStates = [0 for c in range(m)]
    #Ls = [0 for c in range(m)]
    #print('i: %d' % i)
    for j in xrange(n):
        #print('j: %d' % j)
        #print ('SwStates[i][j]:',SwStates[i][j])
        if SwStates[i][j]==1:
            #print ('SwStates[i][j]!=0')
            for k in xrange(m):
                #print('k: %d' % k)
                #print('i',i,'j',j,'k',k)
                #print ('nowStates[k]',nowStates[k])
                #print ('cordStates[j][k]',cordStates[j][k])
                if (nowStates[k]^cordStates[j][k])==1:
                    #Ls[k] = 1
                    nowStates[k] = 1
                else:
                    #Ls[k] = 0
                    nowStates[k] = 0

                #print ('Ls',Ls)

        #nowStates = Ls
    #print ('i',i,'j',j,'nowStates',nowStates)
    LightStates[i] = nowStates

ans = 0
for i in xrange(len(LightStates)):
    if(LightStates[i]==p_list):
        ans+=1;


print ans

Submission status: Accepted

Solution code:
from itertools import product
def resolve():
  N, M = map(int, input().split())
  k = []
  s = []
  for i in range(M):
    s.append(list(map(int, input().split())))
    k.append(s[-1].pop(0))
  p = list(map(int, input().split()))
  ret = 0
  print(sum([1 for st in product(range(2), repeat=N)
       if sum([1 for i in range(M)
               if sum([st[sij-1] for sij in s[i]])%2 == p[i]
              ]) == M
      ]))
resolve()

Submission status: Accepted

Solution code:
# N個のスイッチ
# M個の電球 それぞれKiこのスイッチに繋がる
# スイッチSi(電球)k()
# MとNのルート

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

bulb_lst = []
for m in range(M):
    # 最初は電球が繋がっているスイッチの数
    # sは繋がっているスイッチの番号
    bulb_lst.append(list(map(int, input().split())))

# onになっているスイッチを2で割ったときの求めるあまり
want_switch = list(map(int, input().split()))

# スイッチ全パターン分のON OFFの状態を取得する。
# 特定の状態に対してそれぞれの電球がどうなっているかをチェックする。
# targetのスイッチの点灯状況とそれに伴う電球の点灯状況
# 全ての電球が光っている場合resを増やす

res = 0

for switch_pattern in (list(map(int, bin(i)[2:].zfill(N))) for i in range(2 ** N)):
    flg = True
    # i番目のスイッチが点灯しているかどうか
    for bulb, ws in zip(bulb_lst, want_switch):
        if ws != sum([switch_pattern[con_idx-1] for con_idx in bulb[1:]]) % 2:
            flg = False
            break
    if flg:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(list(map(int,input().split())))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    swi=[]
    for _ in range(n):
        swi.append(i%2)
        i=i//2
    all=0
    for j in range(m):
        cnt=0
        for s in range(1,l[j][0]+1):
            if swi[l[j][s]-1]==1:
                cnt+=1
        if cnt%2==p[j]:
            all+=1
    if all==m:
        ans+=1
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    bn = str(bin(i))[2:].zfill(n)
    bright = 0
    for light in range(m):
        onbotton = 0
        for j, bit in enumerate(bn):
            if (j+1 in s[light])and (bit=='1'): onbotton+=1
        if onbotton%2 == p[light]: bright+=1
    if bright == m: ans+=1
print(ans)