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())
KS = [list(map(int, input().split())) for _ in range(m)]
P = list(map(int, input().split()))

ans = 0
for i in range(2 ** n):
    i_str = bin(i)[2:].zfill(n)
    onNum = 0
    for num, ks in enumerate(KS):
        k = ks[0]
        s = ks[1:]
        p = P[num]
        on = 0
        for sw in s:
            if i_str[sw - 1] == "1":
                on += 1
        if on % 2 == p:
            onNum += 1
    if onNum == m:
        ans += 1

print(ans)

Submission status: Accepted

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

switch_list = []

for i in range(m):
    s  = list(map(int, input().split()))
    s.pop(0)
    switch_list.append(s)
p_list = list(map(int, input().split()))
#print(switch_list)
#print(p_list)

ans = 0

for bit in range(1 << n): #100・・0(n+1桁)-1 =　111・・・1(n桁)となりn桁のビット演算をfor文で回す
    cnt = 0
    for j in range(0,m):
        switch_sum = 0
        for i in range(n):
            if (bit >> i) & 1 and i+1 in switch_list[j]:
                switch_sum += 1
        if switch_sum%2 == p_list[j]:
            cnt += 1
            if cnt == m:
                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 S in range(1 << N):
    res = [pp==0 for pp in p]
    for j in range(N):
        if (S >> j) & 1:
            for l in range(M):
                if j+1 in k[l][1:]:
                    res[l] = not res[l]
    if res == [True] * M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split(' '))
lights=[]
slist=[]

for i in range(M):
  line=input()
  
  switches=list(map(int,line.split(' ')))
  s_bit=0
  for switch in switches[1:]:
    s_bit+=1<<(switch-1)
  slist.append(s_bit)

plist=list(map(int,input().split(' ')))

#print('slist {}'.format(slist))
#print('plist {}'.format(plist))
ans=0
for state_switches in range((1<<N)):
  on_num=0
  #print('====')
  #print(state_switches)
  for k in range(M):
    s_bit=slist[k]
    s_on=s_bit&state_switches
    #print('s_bit state_swithces s_on : {} :{} : {}'.format(s_bit,state_switches,s_on))
    s_num=0
    for i in range(N):
      #print('s_on 1<<i result {} {} {}'.format(s_on,1<<i,s_on&(1<<i))) 
      s_num+=(s_on&(1<<i))>>i
    #print('s_num p {} {}'.format(s_num,plist[k]))
    if s_num%2==plist[k]:
      on_num+=1
    #print(on_num)
  if on_num==M:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()

    n, m = get_int_multi()

    s = []

    for i in range(m):
        wk = get_int_list()
        wk = wk[1:]
        s.append(wk)

    p = get_int_list()

    ans = 0
    for i in range(2 ** n):
        ok = True
        for ii in range(m): # 電球ごとに調査
            count = 0
            for iii in range(n): # スイッチONOFF
                if ((i >> iii) & 1):
                    if (iii+1) in s[ii]:
                        count += 1
            if (count % 2 != p[ii]):
                ok = False
                break
        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):
    b="0"*(N-len(bin(i)[2:]))+bin(i)[2:]
    #print(b)
    on=0
    for j in range(M):#各電球ごと　#電球1はスイッチ1,2,5のうち奇数個ついていればよい
        c=0#その電球に必要なスイッチの数用のカウント
        for k in range(N):
            if k+1 in ks[j][1:]:#例えばスイッチ1が電球1に必要なスイッチのリストふ含まれているとき
                if b[k]=="1":
                    c+=1
        if c%2==p[j]:
            on+=1
    if on==M:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

[N,M] = input().split()
N = int(N)
M = int(M)
a =[]
p = []
list_bin = []

for j in range(M):
    list_temp = [int(s) for s in input().split()]
    list_temp.pop(0)
    for i in range(N):
        if i+1 in list_temp:
            list_bin.append(1)
        else:
            list_bin.append(0)

    a.append(list_bin)
    list_bin = []
p = [int(s) for s in input().split()]

arr_switch = np.array(a)
arr_p = np.array(p)
arr_pattern = np.array(list(itertools.product([0,1], repeat=N)))

count = 0
flag = 1
for switch in arr_pattern:
    for m in range(M):
        if (not (np.dot(switch, arr_switch[m]) % 2 == arr_p[m])) or  (np.dot(switch, np.ones(N)) == -1):
           flag = 0
    if flag == 1:
        count = count + 1
    flag=1
print(count)

Submission status: Accepted

Solution code:
import copy
N,M = map(int,input().split())
num = {}
tmp ={}
tmpli = []
li = []
p = []
count = 0
for i in range(M):
    for i in range(N):
        num[i+1] = 0
    a = list(map(int,input().split()))
    for j in range(len(a)-1):
        if a[j+1] in num:
            num[a[j+1]] += 1
    li.append(num.copy())
p = list(map(int,input().split()))

for i in range(2**N):
    tmpli = copy.deepcopy(li)
    for j in range(N):
        if ((i >> j) & 1):
            for k in tmpli:
                if j + 1 in k:
                    k[j+1] = 0
    tmp = 0
    for b in range(len(p)):
        if sum(tmpli[b].values()) % 2 == p[b]:
            tmp += 1
    if tmp == len(p):
        count += 1
print(count)

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

answer = 0
switch = []
for i in range(2 ** n):
    _switch = [0] * n
    for j in range(n):

        if i >> j & 1 :
            _switch[j]  = 1
    switch.append(_switch)

for i in range(2 ** n):
    flag = True
    for j in range(m):
        light = 0
        for _k  in k[j][1:]:
            light += switch[i][_k - 1]

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

    if flag:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = []
ans = 0
for _ in range(m):
    A.append(list(map(int,input().split())))
P = list(map(int,input().split()))
for bit in range(1<<n):
    flag = True
    for i in range(m):
        cnt = 0
        k,S = A[i][0],A[i][1:]
        for s in S:
            if ((bit>>(s-1))&1) and flag == True:
                cnt += 1
        if cnt %2==P[i]:
            continue
        else:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def mod2(num):
    return num % 2

def solve():
    # 標準入力
    N, M = list(map(int, input().split()))  # N: スイッチの数， M: 電球の数
    k = [0] * M  # 電球iにつながっているスイッチの数
    s = [[0] for _ in range(M)]  # 電球iにつながっているスイッチの番号
    for i in range(M):
        tmp = list(map(int, input().split()))
        k[i] = tmp[0]
        s[i] = tmp[1::]
    p = list(map(int, input().split()))

    # スイッチの状態を総当たり
    count = 0
    for switch_state in range(2**N):
        p_tmp = [0] * M
        iter_num = format(switch_state, '0'+str(N)+'b')
        # 電球ごとに条件をチェック, i: i番目の電球，s_i: i番目の電球に接続しているスイッチのリスト
        for i, s_i in enumerate(s):
            # 電球iに接続しているスイッチs_i_jがon/offかチェック
            for s_i_j in s_i:
                if (iter_num[s_i_j-1] == '1'):
                    p_tmp[i] += 1
        if(p == list(map(mod2, p_tmp))):
            count += 1
    print(count)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
ks=[[] for i in range(m)]
for i in range(m):
    ks[i]=list(map(int,input().split()))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    a=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            a[j]=1
    f=0
    for j in range(m):
        x=0
        for q in range(ks[j][0]):
            
            if a[ks[j][q+1]-1]==1:
                x+=1
        if x%2==p[j]:
            f+=1
    if f==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

ans=0

for i in range(2**N):

    # swにスイッチのオンオフを記録
    sw=[0]*N
    for j in range(N):
        if (i>>j)&1:
            sw[j]=1

    count=0
    for denkyu_no in range(M):
        if sum([sw[ks[denkyu_no][j+1]-1] for j in range(ks[denkyu_no][0])])%2 ==p[denkyu_no]:
            count +=1

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

Submission status: Accepted

Solution code:
import numpy as np
 
N, M = map(int, input().split())
array = np.zeros([M, N])
for i in range(M):
    l = list(map(int, input().split()))
    for j in l[1:]:
        array[i, j-1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for i in range(1<<N):
    array_i = array.copy()
    for j in range(N):
        if i&(1<<j):
            array_i[:, j-1] = 0
    if sum(array_i.sum(1)%2 == p)==M:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools

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


answer_count = 0
for switches in itertools.product((0, 1), repeat=N):
    on_count = 0
    for j in range(M):
        count = 0
        for i in range(N):
            if (switches[i] == 1) and (i + 1 in target_switches[j][1:]):
                count += 1
                
        if count % 2 == p[j]:
            on_count += 1
    
    if on_count == M:
        answer_count += 1

print(answer_count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(M)]
P=list(map(int,input().split()))
c=0
for i in range(2**N):
    A=[0]*N
    for j in range(N):
        if (i>>j&1):
            A[j]=1
    T=True
    for j in range(M):
        s=0
        for k in range(L[j][0]):
            s+=A[L[j][k+1]-1]
        if s%2!=P[j]:
            T=False
    if T:
        c+=1
print(c)

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(2**n):
    ss=[0]*n
    cc=0
    for j in range(n):
        if i>>j&1:
            ss[j]=1
    for j in range(m):
        c=0
        k=s[j][0]
        for l in range(1,k+1):
            c+=ss[s[j][l]-1]
        if c%2==p[j]:
            cc+=1
    if cc==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc128_c

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

res = 0
for i in range(2**N):
    b = format(i, '0' + str(N) + 'b')
    can_light_up = True
    for j in range(M):
        count = 0
        for s in k[j]:
            if b[s-1] == '1':
                count += 1
        if count % 2 != p[j]:
            can_light_up = False
    if can_light_up:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
k = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
s = []
for i in range(n):
    s.append(i)
count = 0
for i in range(n+1):
    for item in itertools.combinations(s, i):
        li = [0] * m
        onoff = [0]*n
        for j in item:
            onoff[j] = 1
        for k_i in range(m):
            c = 0
            for k_j in range(k[k_i][0]):
                if onoff[k[k_i][k_j+1]-1] == 1:
                    c += 1
            if c % 2 == p[k_i]:
                li[k_i] = 1
        if all(li):
            count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
state = []
for _ in range(M):
  lst = list(map(int, input().split()))
  state.append(lst[1:])#switch numbers each denkyu
p = list(map(int, input().split()))#numbers switches on %2 == pi 
ans = 0
for i in range(2**N):
  total = 0
  for j in range(M):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:#全スイッチのパターン一つ一つについて、各電球の各スイッチがオンになっているか
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
    else:
      break
  if total == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
state = []
for _ in range(M):
  lst = list(map(int, input().split()))
  state.append(lst[1:])#switch numbers each denkyu
p = list(map(int, input().split()))#numbers switches on %2 == pi 
ans = 0
for i in range(2**N):
  total = 0
  for j in range(M):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:#全スイッチのパターン一つ一つについて、各電球の各スイッチがオンになっているか
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
  if total == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    connected = []
    for i in range(m):
        row = LI()
        swithes = row[1:]
        connected.append(swithes)
    p = LI()
    ans = 0
    for i in range(2 ** n):
        i_str = format(i, f"0{n}b")
        is_ok = True
        for m_idx in range(m):
            sum_1 = 0
            for swith in connected[m_idx]:
                if i_str[swith - 1] == "1":
                    sum_1 += 1

            if sum_1 % 2 != p[m_idx]:
                is_ok = False
                break

        if is_ok:
            ans += 1

    print(ans)


main()

Submission status: Accepted

Solution code:
# C - Switches
#bit全探索の練習問題
import copy

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

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

KS = []
for m in range(M):#列の数はМ
    box = list()
    for n in range(len(ks[m])):#M列の要素を数字に直す処理
        ks[m][n] = int(ks[m][n])
        box.append(ks[m][n])
    KS.append(box)            

swich = []
for o in range(M):#列の数はМ
    swi = list()
    for r in range(1,len(KS[o])):#k以外を取り出す
        swi.append(ks[o][r])
    swich.append(swi)
           
ans = 0
for i in range(1<<N):#全パターンは2**(スイッチの総数)
    SWICH = copy.deepcopy(swich)
    light_on = 0
    for j in range(N):
        mask = 1<< j#1をj個左にずらした2進数
        if i & mask != 0:#スイッチjがonの時
            continue
        else:#スイッチjがoffの時
            for y in range(M):#電球iごとに繰り返し
                if (j+1 in SWICH[y]) == True:#スイッチsiが電球iに接続されているとき
                    SWICH[y].remove(j+1)

    #onのみがSWICHに入っている
    flat_SWICH = []
    for a in range(len(SWICH)):
        for b in range(len(SWICH[a])):
            flat_SWICH.append(SWICH[a][b])
            
    for x in range(M):
        if (len(SWICH[x]) % 2) == p[x]:#onのスイッチの数を2で割った余りがPの値と等しい時
            light_on += 1
    if light_on == M:#onの電球の個数がMと等しい(全てon)時
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
array = np.zeros([M, N])
for i in range(M):
    l = list(map(int, input().split()))
    for j in l[1:]:
        array[i, j-1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for i in range(1<<N):
    array_i = array.copy()
    for j in range(N):
        if i&(1<<j):
            array_i[:, j-1] = 0
    if sum(array_i.sum(1)%2 == p)==M:
        count += 1
print(count)

Submission status: Accepted

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

for i in range(M):
    switches_bulbs_connection[i] = list(map(int, input().split()))[1:]
p = list(map(int, input().split()))
count = 0
flag = 0

for i in range(2 ** N):  # スイッチのon/offについてビット全探索
    switch_on_off = [0] * N
    bulb_stat = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            switch_on_off[j] += 1  # 各スイッチがonかoffか
    for k in range(M):  # 電球kについて調べる
        tmp = switches_bulbs_connection[k]
        for switch in tmp:
            if switch_on_off[switch-1]:
                bulb_stat[k] += 1
    for l in range(M):
        if bulb_stat[l] % 2 == p[l]:
            flag += 1
    if flag == M:
        count += 1
    flag = 0

print(count)

Submission status: Accepted

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

ans = 0
for x in range(2**n):
  for i in range(m):
    cnt = 0
    for j in range(n):
      if (x >> j & 1) and s[i][j]:
        cnt += 1
    if cnt % 2 != p[i]:
      break
  else:  # breakしなかった=すべて一致した場合のみ
    ans += 1
print(ans)

Submission status: Accepted

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

S=[[] for _ in range(N+1)]
for i in range(M):
    T=list(map(int,input().split()))
    for x in T[1:]:
        S[x].append(i+1)

P=["*"]+list(map(int,input().split()))

X=0
for i in range(2**N):
    Q=["*"]+[0]*M
    for x in range(N):
        if i%2:
            for k in S[x+1]:
                Q[k]=(Q[k]+1)%2
                
        i>>=1
    X+=(P==Q)
print(X)

Submission status: Accepted

Solution code:
N,M = map(int,input().split()) #Nスイッチ、M電球
K = []; S = []
for i in range(M):
  k, *s = map(int,input().split())
  for j in range(len(s)): #スイッチを0index
    s[j] -= 1 
  K.append(k)
  S.append(s)
#print(S)
#print(K)
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
  Switch= [0 for _ in range(N)]
  for j in range(N): #j個目が押されているか？
    if(i>>j)&1==1:
      Switch[j] = 1
  num = 0
  for k in range(M): #k個目の電球がついているか？
    temp = 0
    for x in S[k]:
      if Switch[x] == 1:
        temp += 1
    if temp%2 == P[k]:
      num += pow(2,k)
  #print(num)
  if num == pow(2,M)-1:
    ans += 1
print(ans)

Submission status: Accepted

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

res = 0
# bit列の組み合わせについて
for bit in range(1 << n):
    ok = True
    # 各電球について
    for i in range(m):
        # 電球iのonの状態のスイッチの個数
        cnt = 0
        # 電球の各スイッチについて
        for v in lights[i]:
            v -= 1
            # 電球のスイッチがvのon/off判定
            if bit & (1 << v):
                cnt += 1
        # 電球iは点灯しているか判定
        if cnt % 2 != P[i]:
            ok = False
    if ok:
        res += 1
print(res)

Submission status: Accepted

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

cnt = 0
for i in range(2**N):
    b = [0]*N
    for j in range(N):
        if ((i >> j) & 1):
            b[j] = 1
    
    for k in range(M):
        num = 0
        for l in range(len(light[k])-1):
            num += b[light[k][l+1]-1] 
        if num%2 != p[k]:
            break
    else: cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n,m = map(int, input().split())
sw = [[int(i) - 1 for i in input().split()] for _ in range(m)]
p = np.array([int(i) for i in input().split()])
x = np.full_like(p, -1)

s_l = itertools.product(np.array([True,False]), repeat = n)
ans = 0
for si in s_l:
    si = np.array(si)
    for mi in range(m):
        x[mi] = si[sw[mi][1:]].sum() % 2
    if np.all(p == x):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
s=[]
for _ in range(M):
    s.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
ans=0
for bit in itertools.product([0,1],repeat=N):
    count=[0]*M
    for light in range(M):
        for k in s[light]:
            count[light]+=bit[k-1]
    if all (count[i]%2==p[i] for i in range(M)):
        ans+=1
print(ans)

Submission status: Accepted

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

# N個のスイッチのon/offの組み合わせを全て探索し、すべて点灯するものをカウント

N,M = map(int,readline().split())
lights = [None] * M
for i in range(M):
  lights[i] = list(map(int,readline().split()))[1:]
  
P = list(map(int,readline().split()))

ans = 0
for i in range(2 ** N):
  for j in range(len(lights)):
    # 電球jが点灯するかチェック
    cnt = 0
    for k in range(len(lights[j])):
      # スイッチを一つ一つ確認
      # onになっているか？
      if (i >> lights[j][k] - 1) & 1:
        # onになっている
        cnt += 1
    if cnt % 2 != P[j]:
      break
  else:
    ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for idx in range(2**n):
    switch_on = [False] * n
    for s in range(n):
        if 2**s & idx > 0:
            switch_on[s] = True

    ok = True
    # ビット上位がN，下位が1
    for lamp in range(m):
        num_on_switch = 0
        for s in switches[lamp - 1][1:]:
            if switch_on[s-1] == True:
                num_on_switch += 1
        
        if num_on_switch % 2 != ps[lamp-1]:
            ok = False
        if not ok:
            break
    
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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

k = []
s_l = []
for _ in range(m):
    l = list(map(int, input().split()))
    k.append(l[0])
    s_l.append(l[1:])

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

ans = 0
for i in range(2**n):
    valid = 1
    for j in range(m):
        on = 0
        for s in s_l[j]:
            on += (i >> (s-1) & 1)
        if on % 2 == p[j]:
            valid *= 1
        else:
            valid *= 0
    ans += valid

print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N,M = map(int,input().split())
K = [list(map(int,input().split()))[1:] for m in range(M)]
P = list(map(int,input().split()))
print(sum([all([sum([s[j-1] for j in v])%2==t for v,t in zip(K,P)]) for s in product([0,1],repeat=N)]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = []
for _ in range(M):
  k, *S = map(int, input().split())
  L.append(S)
P = list(map(int, input().split()))
c = 0
for i in range(2**N):
  A = []
  for j in range(N):
    if (i>>j)&1:
      A.append(j+1)
  A = set(A)
  for i in range(M):
    if len(A&set(L[i]))%2!=P[i]:
      break
  else:
    c += 1
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
num=[]
for i in range(m):
    num.append(list(map(int,input().split())))
num3=[[] for _ in range(n)]
for i in range(m):
    for j in range(1,num[i][0]+1):
        num3[num[i][j]-1].append(i+1)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    num2=[0]*m
    num4=0
    for j in range(n):
        if (i>>j) & 1:
            for k in range(len(num3[j])):
                num2[num3[j][k]-1]+=1
    for j in range(m):
        if num2[j]%2!=p[j]:
            num4=1
            break
    if num4==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# bit全順列列挙
def bitall(n):
    parm = []
    for i in range(1<<n): # 0/1の組み合わせは1<<n(=2**n)通り存在。
        on = [0 for _ in range(n)] # とりあえず全て0にしておく。
        
        for j in range(n):
            if i & (1<<j): # iのj桁目が1となっている場所をonにする。
                on[j] = 1
                
        parm.append(on)
                
    return parm


N, M = map(int, input().split())
K = []
S = []
for m in range(M):
    tmp = list(map(int, input().split()))
    K.append(tmp[0])
    S.append(tmp[1:])
P = list(map(int, input().split()))

swi_parms = bitall(N)
ans =0

for swi_parm in swi_parms:
    flag = 0
    for k in range(len(K)):
        cnt = 0
        
        for s in S[k]:
            # 対応するスイッチのon数をカウント
            if swi_parm[s-1] == 1: cnt += 1
        
        if cnt%2 == P[k]:
            continue
        else:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
D=[]
for i in range(M):
  D.append(list(map(int,input().split())))
  D[-1]=D[-1][1:]
L=list(map(int,input().split()))
count=0
s=[]
for i in range(2**N):
  p = True
  for j in range(M):
    tmp = 0
    for k in range(N):
      if i>>k & 1:
        if k+1 in D[j]:
          tmp+=1
    if not L[j] == tmp%2:
      p = False
      break
  if p:
    s.append(bin(i))
    count+=1
print(count)

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=[int(x) for x in input().split()]
#print(ks)

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in range(M):
        j_on_cnt=0
        for k in ks[j][1:]:
            j_on_cnt+=i[k-1]
            
        if j_on_cnt%2 != p[j]:
            ok=False
            break
    if ok:
        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=[int(x) for x in input().split()]

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in range(M):
        j_on_cnt=0
        for k in ks[j][1:]:
            j_on_cnt+=i[k-1]
            
        if j_on_cnt % 2!=p[j]:
            ok=False
            break
    if ok:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = (int(xi) for xi in input().split())
k = []
for xi in range(m):
    ksub = [int(xi) for xi in input().split()]
    k.append(ksub[1:])
p = [int(xi) for xi in input().split()]

# print(k)


countN = 0
for Nnum in range(2**n):
    txt = bin(Nnum)[2:]
    txt = "0"*(n-len(txt))+txt
    # print(txt)

    for li in range(m):
        ltxt = "0"*n
        for xi in range(len(k[li])):
            point = k[li][xi]-1
            ltxt = ltxt[:point]+"1"+ltxt[point+1:]
        # print(ltxt)
        count = 0
        for xi in range(n):
            if txt[xi]=="1" and ltxt[xi]=="1":
                count += 1
        if count%2==p[li]:
            switch = True
        else:
            switch = False
            break
    if switch: countN += 1

print(countN)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dic = {}
for i in range(m):
    s = list(map(int,input().split()))[1:]
    dic[i] = s
P = list(map(int,input().split()))
# print(dic)

ans = 0

# ON/OFFをbit全探索
for i in range(2**n):
    on_off = [False]*n
    for j in range(n):
        if ((i>>j)&1):
            on_off[j] = True
    flag = True
    for k in range(m):
        cnt = 0
        for l in dic[k]:
            if on_off[l-1]:
                cnt += 1
        if cnt % 2 != P[k]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[15]:


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


# In[16]:


ans = 0
for s in range(2**N):
    s_bit = format(s,"010b")
    for i,item in enumerate(ks):
        cnt = 0
        for x in item[1:]:
            if s_bit[10-x] == "1":
                cnt += 1
        if cnt%2 != p[i]:
            break
    else:
        ans += 1
        continue
print(ans)


# In[ ]:

Submission status: Accepted

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

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

count = 0

for i in range(2**n):
    b = bin(i)
    sw = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            sw[j] = True

    boollist = []
    for j in range(m):
        k = lis[j][0]
        sl = lis[j][1:]
        total = 0

        for x in sl:
            if sw[x-1]:
                total += 1
        
        if total % 2 == p[j]:
            boollist.append(1)
        else:
            boollist.append(0)
    
    if all(boollist):
        count += 1

print(count)

Submission status: Accepted

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

for i in range(m):
    tmp = []
    tmp = list(map(int,input().split()))
    s_list.append(tmp)

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

ans = 0

for i in range((2**n)):
    bin_i = [int(x) for x in bin(i)[2:]]
    while len(bin_i) != n:
        bin_i.insert(0,0)
    flag = 0
    for j in range(m):
        tmp = 0
        for k in range(1,s_list[j][0]+1):
            tmp += bin_i[s_list[j][k]-1]
        if tmp%2 != p_list[j]:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

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

answer = 0
from itertools import product

for sw in product([0, 1], repeat=N):
    for p, ks in zip(P, KS):
        K = ks[0]
        S = ks[1:]
        if sum([sw[s - 1] for s in S]) % 2 != p % 2:
            break
    else:
        answer += 1

print(answer)