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 math
import copy
import fractions
import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

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

status = getSomeInputListInt(m)
condition = getInputListInt()

ans = 0
mask = []

for i in range(len(status)):
    mask.append(0b0)
    for j in range(1, status[i][0]+1):
        tmp = 1
        tmp = tmp << (status[i][j] - 1)
        mask[i] = mask[i] | tmp

for i in range(2**n):
    flg = True
    for j in range(m):
        masked = i & mask[j]
        oneCnt = bin(masked).count("1")
        if oneCnt % 2 != condition[j]:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Switch = [0] * N
for i in range(M):
  k,*S = map(int,input().split())
  for s in S:
    s -= 1
    Switch[s] |= (1 <<i)
#print(Switch)
P = list(map(int,input().split()))
p = 0
for i in range(M):
  p |= (P[i] <<i)
#print(p)

ans = 0
for i in range(2 ** N):
  light = 0
  for j in range(N):
    if (i >>j) & 1 == 1:
      light ^= Switch[j]
  if light == p:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ABC 128, C

def f(X, Y):
    return(len(X.intersection(Y)) % 2)

n, m = [int(el) for el in input().split(' ')]


T = []
for i in range(m):
    S = set()
    tmp = [int(el) for el in input().split(' ')]
    for j in range(1, len(tmp)):
        S.add(tmp[j])
    T.append(S)
P = [int(el) for el in input().split(' ')]



total = 0
for i in range(2**n):
    pattern = set()
    for j in range(n):
        if ((i >> j) & 1):
            pattern.add(j+1)
    
    if all([P[k] == f(T[k], pattern) for k in range(m)]):
        total += 1
print(total)

Submission status: Accepted

Solution code:
N,M = [int(s) for s in input().split()]
light=[0 for i in range(M)]
for i in range(M):
  lst= [int(s) for s in input().split()]
  light[i]=lst
mod= [int(s) for s in input().split()]
swi=[[]]
for i in range(N):
  p0=[s+[0] for s in swi]
  p1=[s+[1] for s in swi]
  swi=p0+p1
count=0
for i in range(2**N):
  flag=1
  for j in range(M):
    k=light[j][0]
    add=0
    for l in range(1,k+1):
      add=add+swi[i][light[j][l]-1]
    if(add%2!=mod[j]):
      flag=0
      break
  count=count+flag
print(count)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c
# C - Switches
from itertools import product

n, m = list(map(int, input().split()))
k_list = []
s_list_list = []

for _ in range(m):
    k, *s = list(map(int, input().split()))
    k_list.append(k)
    s_list_list.append(s)

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

# スイッチの点灯の組み合わせは最大で100
s_p_list = product([0, 1], repeat=n)
c = 0
match_list = []
for s_p in s_p_list:

    is_match = True
    for i, s_list in enumerate(s_list_list):
        w = sum([s_p[s-1] for s in s_list])
        if w % 2 != p_list[i]:
            is_match = False
            break
    if is_match:
        c += 1
        match_list.append(s_p)

print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in range(1, m+1):
    k, *to_swi = map(int, input().split())
    if k == 1:
        list(to_swi)
    for swi in to_swi:
        dic[swi].append(i)

P = [0] + list(map(int, input().split()))
count = 0
for i in range(2**n):
    rights = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            for right in dic[j+1]:
                rights[right] += 1
                rights[right] %= 2

    if rights == P:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

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

#ON, OFFの全組み合わせ
c = list(itertools.product(range(2), repeat = N))

#電球の付き方がj(y)のとき電球i(x)が光るか否か
def l(x, y):
    switch_on = 0
    for i in range(k[x]):
        switch_on += c[y][s[x][i] - 1]
    if switch_on % 2 == p[x]:
        return 1
    else:
        return 0

ans = 0
for j in range(2 ** N):
    light_on = 0
    for i in range(M):
        light_on += l(i, j)
    if light_on == M:
        ans += 1
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
import sys

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
# 電球iがつながっているスイッチに関するリストが得られる
# xorを使うと効率的に解けた気がするが...
# xor (1,1) = 0, (0, 0) = 0 / (1, 0) = 1, (0, 1) = 1
if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    L = [list(map(int,list(sys.stdin.readline().split()))) for i in range(M)]
    cond = list(map(int, sys.stdin.readline().split()))

    cnt = 0
    for sw_bit in range(1 << N):
        flag = True
        for l, c in zip(L, cond):
            bit = 0
            for e in l[1::]:
                bit |= (1 << (e - 1))
            # 点灯判定を上手くやりたい
            bit &= sw_bit
            if bin(bit).count("1") % 2 != c:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    f = 1
    for j in range(m):
        g = 1
        g &= (sum([int(bin(i>>(u-1)),2) for u in s[j]])%2 == p[j])
        f &= g
    ans += f
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
s = [None for _ in range(m)]

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

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

ans = 0
for tpl in product([0, 1], repeat=n):
    for i in range(m):
        cnt = 0
        is_on = True
        for j in range(s[i][0]):
            if tpl[s[i][j + 1] - 1] == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            is_on = False
            break
    if is_on:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
d={}
for i in range(M):
    a,*b=map(int,input().split())
    d[i]=b
p=list(map(int,input().split()))
cnt=0
for i in range(2**N):
    t=bin(i)[2:]
    t='0'*(N-len(t)+1)+t
    t=list(t)
    f=True
    for j in range(M):
        s=0
        for k in d[j]:
            s+=int(t[k])
        if s%2!=p[j]:
            f=False
            break
    if f:cnt+=1
print(cnt)

Submission status: Accepted

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

def main(): 
    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 bit in range(2**N):
        Flag = True
        for i in range(M):
            count = 0
            for j in range(1,ks[i][0]+1):
                if bit & (1<<ks[i][j]-1):
                    count += 1
            if count%2!=p[i]:
                Flag = False
                break
        if Flag:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product


def main():
    N, M = map(int, input().split())
    conn = [
        list(map(int, input().split()[1:]))
        for _ in range(M)
    ]
    conds = list(map(int, input().split()))

    print(len([
        state
        for state in product(("ON", "OFF"), repeat=N)
        if all(
            len([s for s in switches if state[s - 1] == "ON"]) % 2 == p
            for switches, p in zip(conn, conds)
        )
    ]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product


def main():
    N, M = map(int, input().split())
    conn = [
        list(map(int, input().split()[1:]))
        for _ in range(M)
    ]
    conds = list(map(int, input().split()))

    ans = 0
    for state in product(("ON", "OFF"), repeat=N):
        if all(
            len([s for s in switches if state[s - 1] == "ON"]) % 2 == p
            for switches, p in zip(conn, conds)
        ):
            ans += 1
            
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from numpy import*
n,m=map(int,input().split())
l=[]
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())
 
ans=0
for t in range(2**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Submission status: Accepted

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

switch_sum = 0
switch_ptn = 0
switch_ptn2 = 0

#スイッチのOnOffパターン
for i in range(2**N):
  i_2 = str(bin(i))[2:]
  i_bit = i_2.zfill(N)
  
  #各電球のスイッチパターンを確認
#  print(i_bit)
  for j in range(M):
    for k in range(1,K[j][0]+1):
      switch_sum += int(i_bit[K[j][k]-1])
    switch_sum = switch_sum%2
#    print(switch_sum,P[j])
    if switch_sum == P[j]:
      switch_ptn += 1
    switch_sum = 0
  if switch_ptn == M:
    switch_ptn2 += 1
  switch_ptn = 0
    
print(switch_ptn2)

Submission status: Accepted

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

cnt = 0
for i in range(0, 2**n):
    ptn = '0'+format(i, '010b')[::-1]
    light = []
    for j, sw in enumerate(s):
        on_sws = [ptn[sw_i] for sw_i in sw if ptn[sw_i] == '1']
        light.append(len(on_sws) % 2 == int(p[j]))
    if all(light):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# スイッチの数、電球の数
N,M = map(int, input().split())
# 電球に紐づいたスイッチの情報を持つリスト
l1 = [0]*M;
for i in range(M):
  l1[i] = list(map(int, input().split()))
# 各電球の点灯条件を持つリスト
l2 = list(map(int,input().split()))
anser = 0
# スイッチのパターンをループでまわす
for i in range(2**N):
  isAll = True
  switch = '{:010b}'.format(i)
  #　各電球が点灯するか判定
  for j in range(M):
    #print('電球'+str(j))
    # スイッチがonになっている個数のカウンター
    count = 0
    # 電球に紐づくスイッチがonになっているかの判定
    for k in range(l1[j][0]):
      # print('スイッチ番号',l1[j][k+1])
      # print('スイッチの状態',switch[9-div:10-div])
      div = l1[j][k+1]-1
      if int(switch[9-div:10-div]) == 1:
        count += 1
    if count%2 != l2[j]:
      isAll = False
      break
  if isAll:
    anser += 1
print(anser)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
depends = []
for i in range(m):
    depends.append([ int(i)-1 for i in input().split() ])
p = [ int(i) for i in input().split() ]
ans = 0
for i in range(2**n):
    chosen = set()
    for j in range(n):
        if i & (1<<j):
            chosen.add(j)
    # Now in this iteration we have chosen those element in chosen
    ok = 0
    for j in range(m):
        # Required count
        req = p[j]
        cnt = 0
        for k in range(1,depends[j][0]+2):
            if depends[j][k] in chosen:
                cnt += 1
        if cnt % 2 == req:
            ok += 1

    if ok == m:
        ans += 1
print(ans)

Submission status: Accepted

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

def main():
    N,M=map(int, input().split())

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

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

    ans = 0
    for i in range(2**N):
        b = True
        for j in range(M):
            if "{:b}".format(i&K[j]).count("1") %2 != P[j]:
                b = False
                break
        if b:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N,M=map(int, input().split())
    K=[]
    for i in range(M):
        K.append(list(map(int, input().split())))
    P = list(map(int, input().split()))

    ans = 0
    for i in range(2**N):
        s = "{:0" + str(N) +"b}"
        b = True
        for j in range(M):
            x = 0
            for k in K[j][1:]:
                x += int(2**(N-k))
            s = "{:b}".format(i&x)
            if s.count("1")%2 != P[j]:
                b = False
                break
        if b:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(2**N):
    p = [0]*N
    tmp = i
    for j in range(N):
        if tmp%2 == 1:
            p[j] = 1
        tmp //= 2
    flag = 0
    for j in range(M):
        count = 0
        for k in range(len(A[j])-1):
            if p[A[j][k+1]-1] == 1:
                count += 1
        if not count%2 == P[j]:
            flag = 1
    if flag == 0:
        answer += 1
    
print(answer)

Submission status: Accepted

Solution code:
from functools import reduce
import math

N, M = [int(a) for a in input().split()]
s = []
bulb_list = []

for i in range(M):
  line = [int(a) for a in input().split()]
  k = line[0]
  s.append([int(x) for x in line[1:k+1]])
  bulb_list += s[i]

#print(list(set(bulb_list)))
p = [int(a) for a in input().split()]
#print(s)
count = 0

for i in range(int(math.pow(2, N))):
  onoff = format(i, '010b')
  ok = True
  #print('---')
  #print(onoff)
  for j in range(M):
    l = list(map(lambda x: int(onoff[-x]), s[j]))
    mod = reduce(lambda a, b: a+b, l) % 2
    #print(j, s[j], l, p[j], mod)
    if mod != p[j]:
      ok = False
      break
  if ok:
    #print('ok')
    count += 1

print(count)

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):
    switch = format(i, '010b')
    switch = switch[-N:]
    cn = 0
    for j in range(M):
        t = s[j]
        count = 0
        for k in t[1:]:
            if int(switch[k-1]) == 1:
                count += 1
        if count % 2 == p[j]:
            cn += 1
    if cn == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

sw = [[] for _ in range(M)]
for i in range(M):
    sw[i] = list(map(int,input().split()[1:]))

P = list(map(int,input().split()))
ans = 0
for tpl in itertools.product([0,1], repeat=N):
    bl = True
    for i in range(M):
        s = sum([tpl[j-1] for j in sw[i]])
        if (s-P[i])%2 == 1:
            bl = False
            break
    if bl:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    switches = []
    for _ in range(M):
        tp = list(map(int, input().split()))
        temp = [int(x) for x in tp[1:]]
        switches.append(temp)

    P = [int(p) for p in input().split()]
    d = dict()
    for i in range(M):
        for j in range(len(switches[i])):
            sw = switches[i][j]
            if sw not in d: d[sw] = [i]
            else: d[sw].append(i)

    states = dict()
    # on = 1, off = 0
    ground = tuple([(P[i]+1) % 2 for i in range(M)])
    states[ground] = 1
    for sw in range(1, N+1):
        if sw in d:
            new = dict()
            for s in states:
                st = list(s)
                for j in d[sw]:
                    st[j] = (st[j]+1) % 2
                st = tuple(st)
                new[st] = new.get(st, 0) + states[s]
            for st in new:
                states[st] = states.get(st, 0) + new[st]
        else:
            for s in states:
                states[s] *= 2
        # print(sw, states)
    # print(states)
    final = tuple([1 for _ in range(M)])
    return states.get(final, 0)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from itertools import product

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

switches = [(0, 1) for _ in range(n)]
ans = 0
for state in product(*switches) :
    bulbs = [0 for _ in range(m)]
    for i, ((_, *ss), p) in enumerate(zip(ksskss, pp)) :
        p ^= 1
        for s in ss :
            if state[s-1] :
                p ^= 1
        if p :
            bulbs[i] = 1
    if all(bulbs) :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
switches=[]
for i in range(M):
  switch=list(map(int,input().split()))
  switch=switch[1:]
  switches.append(switch)
P=list(map(int,input().split()))
ans=0
def check_d(bottun):
  for i in range(M):
    b_c=0
    for j in switches[i]:
      if (bottun>>(j-1)) & 1 == 1:
        b_c+=1
    if b_c%2!=P[i]:
      return 0
  return 1
    
for bottun in range(2**N):
  ans+=check_d(bottun)
print(ans)

Submission status: Accepted

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

ans = 0
for bits in range(1<<n):
    all_on = True
    for i in range(m):
        pow = 0
        for j in range(1, switch[i][0]+1):
            pow += (bits >> (switch[i][j]-1)) & 1
        if pow % 2 != p[i]:
            all_on = False
            break

    if all_on:
        # print(''.join([str((bits>>i)&1) for i in range(n)]))
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as combi
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
def check(s):
  for i in range(M):
    temp = 0
    for j in range(1, S[i][0] + 1):
      if S[i][j] in s:
        temp += 1
    if temp % 2 != p[i]:
      return False
  return True
res = 0
for i in range(0, N + 1):
  for com in combi(range(1, N + 1), i):
    if check(set(com)) == True:
      res += 1
print(res)

Submission status: Accepted

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

x = 2 ** N

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

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

ans = 0

for i in range(x):
    str_i = str(bin(i))[2:].zfill(N)
    flag = True
    for j in range(M):
        ks_j = ks[j]
        on_sum = 0
        for k in range(ks_j[0]):
            if(str_i[ks_j[k+1]-1] == '1'):
                on_sum += 1
        if(on_sum % 2 != p[j]):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

Submission status: Accepted

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

res = 0
for i in range(2**n):
    format_string = '0' + str(n) + 'b'
    i_str = format(i, format_string)
    for k, lamp in enumerate(lst):
        count = 0
        r = p_lst[k]
        for switch in lamp[1:]:
            count += int(i_str[switch-1])
        if r != count % 2:
            #print('NG: ', i)
            break
    else:
        #print('OK: ', i)
        res += 1
print(res)

Submission status: Accepted

Solution code:
ans=0
n,m=map(int,input().split())
l1=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
for i in range(2**n):
    a=[]
    for j in range(n):
        if i>>j&1:
            a.append(j+1)
    for j in range(m):
        if len(set(a)&set(l1[j][1:]))%2==p[j]:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

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):
  sl = []
  for j in range(N):
    if (i>>j)&1:
      sl.append(j+1)
  for j in range(M):
    if len(set(KS[j][1:])&set(sl))%2 ==P[j]:
      continue
    else:
      break
  else:
    ans += 1
    
print(ans)

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
# (0, 1, 2, ... 2^n-1) の部分集合の全探索（0を含むので合計2^n個)
# 例えば8なら、000〜111までの全部なので、スイッチの全パターンをなめる
for b in range(1<<N):  # 2**nでも一緒
    # 縦軸（M個の電球）→ スイッチ0の電球全部、スイッチ1の電球全部, ...
    for i in range(M):
        c = 0

        # スイッチ番号を順番に取得
        for s in src[i][1:]:
            # bにswitch_num番目のフラグがたってるか？
            # つまり、全探索のなかで、ビットがたってたら「処理をする」というだけ
            switch_num = s-1

            # どうせ全部なめるので、どっちでもいい
#            if b & (1<<(switch_num)):
            if (b >> switch_num) & 1 == 1:
                c += 1

        if c%2 != P[i]:
            break
    else:
        # 割り切れたらその電球は点いてるのでカウント対象
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
bits = [0]*n
for switch_state in range(2**n):
    swi_bin = str(bin(switch_state))
    for i in range(n):
        bits[i] = int(swi_bin[-1-i] if i < len(swi_bin) and swi_bin[-1-i] != 'b' else 0)
    for i in range(m):
        cnt_on = 0
        for s in swi[i]:
            cnt_on += bits[s-1]
        if cnt_on%2 != p[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    temp = list(map(int, input().split()))
    K.append(temp[0])
    S.append(temp[1:len(temp)])
p = list(map(int, input().split()))

L = list(itertools.product([0,1], repeat=N))
ans=0
for l in L:
    i=0
    ans_count = 1
    for s in S:
        c=0
        for j in range(K[i]):
            c += l[s[j]-1]
        if c%2!=p[i]:
            ans_count=0
        i+=1
    ans+=ans_count
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    test = list(bin(i))
    test.pop(0)
    test.pop(0)
    for k in range(n-len(test)):
        test.insert(0,"0")
    temp = True
    for k in range(m):
        counter = 0
        for j in range(switch[k][0]):
            if test[switch[k][j+1]-1] == "1":
                counter += 1
        if p[k] != counter%2:
            temp = False
            break
    if temp:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from itertools import product
N,M = II()
k = [0]*M
p = [0]*M
s = []
for i in range(M):
    a = III()
    k[i] = a[0]
    temp = a[1:]
    temp = list(map(lambda x:x-1,temp))
    s.append(temp)

p = III()

x=list(product([0,1],repeat=N))
count = 0

for i in range(len(x)):
    for j in range(M):
        scount = 0
        for k in s[j]:
            if x[i][k]==1:
                scount += 1
        if scount%2 != p[j]:
            break
        if j==M-1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = (int(i) for i in raw_input().split())
switches = []
for i in range(m):
    line = [int(i) for i in raw_input().split()]
    switches.append(line[1:]) 
ps = [int(i) for i in raw_input().split()]
ans = 0
for i in range(2 ** n):
    pattern = []
    for d in range(n):
        if (1 << d) & i:
            pattern.append(True)
        else:
            pattern.append(False)

    ok = True
    for j in range(m):
        count = 0
        for k in switches[j]:
            if pattern[k-1]:
                count += 1
        ok = ok and (count % 2 == ps[j])
    if ok:
        ans += 1
print ans

Submission status: Accepted

Solution code:
#電球クラス
class Light:
    def __init__(self,name,switchs,whattype):
        self.name=name
        self.switchs=switchs
        self.whattype=whattype
    def reset(self):
        sumnum=0
        for switch in self.switchs:
            sumnum+=switch.onoff
        if sumnum%2==self.whattype:
            self.state="on"
        else:
            self.state="off"
            
#スイッチクラス            
class Switch:
    def __init__(self,name):
        self.name=name
        self.onoff=0
    def click(self,onoff):
        self.onoff=onoff
        
    
#整理用データ
n,m=[int(i) for i in input().split()]
allist=[]
for i in range(m+1):
    allist.append([int(j) for j in input().split()])
      

#全スイッチのリスト
switchlist=[]
for i in range(n):
    switchlist.append(Switch(i))


#全電球のリスト
lightlist=[]
for i in range(m):
    swlist=[]
    swnum=allist[i][1:]
    for j in swnum:
        swlist.append(switchlist[j-1])
    whattype=allist[-1][i]
    lightlist.append(Light(i,swlist,whattype))
    
#全部の付け方について
count=0
clicklist=[0 for i in range(n)]    
for i in range(2**n):
    onoffcheck=0
    j=0
    while i:
        clicklist[j]=i%2
        i=i//2
        j+=1
    for k in range(n):
        switchlist[k].click(clicklist[k])
    for light in lightlist:
        light.reset()
        if light.state=="off":
            onoffcheck+=1
    if onoffcheck==0:
        count+=1
print(count)

Submission status: Accepted

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

ks_nums = [0]*m
for i in range(m):
    for j in range(ks[i][0]):
        ks_nums[i] += 2**(ks[i][j+1]-1)

ans = 0
success = True
for i in range(2**n):
    for j in range(m):
        cnt = 0
        tmp = i & ks_nums[j]
        for k in range(n):
            if ( tmp >> k ) & 1:
                cnt += 1
        if p[j] != cnt % 2:
            success = False
            break
    if success:
        ans += 1
    else:
        success = True

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M=map(int, input().split())
ks=[]
for _ in range(M):
    k,*s=input().split()
    ks.append((k, list(map(int, s))))
P=list(map(int, input().split()))
ans = 0

for i in range(2**N):
	Nb = format(i, 'b')
	Nb = Nb.zfill(N)
	
	for j in range(M):
		s = ks[j][1]
		on = 0

		for k in s:			
			if Nb[k - 1] == '1':
				on += 1

		if on % 2 != P[j]:
			break

	else:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
for i in range(m):
  l = list(map(int,input().split()))
  l.remove(l[0])
  k.append(l)
p = list(map(int,input().split()))
#print(k)
arr = [0]*m
ans = 0
for i in range(2**n):
  flag = 0
  b = str(format(i, '010b'))
  for j in range(m):
    g = int(p[j])
    for h in k[j]:
      g += int(b[10-h])
    if g % 2 == 1:
      flag = 1
      break
  if flag == 0:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
n,m = list(map(int,input().split()))
ki = []
sk = []
for _ in range(m):
    temp = list(map(int,input().split()))
    ki.append(temp[0])
    sk.append(temp[1:])
pm = list(map(int,input().split()))
# Mが10以下なので、全探索を行う

import copy
switch_mask = []
for i in range(2**(n)):
    switch_mask.append(format(i,"0{}b".format(n)))

def is_all_on(mask):
    for i,s in enumerate(sk):
        s_sum = 0
        for connected_switch in s:
            s_sum += int(mask[connected_switch-1])
        if s_sum % 2 != pm[i]:
            return 0
    return 1
ret = 0
for mask in switch_mask:
    ret += is_all_on(mask)
print(ret)

Submission status: Accepted

Solution code:
from functools import reduce
n, m = map(int, input().split())
s = [[int(e) for e in input().split()[1:]] for _ in range(m)]
p = [int(e) for e in input().split()]
t = [reduce(lambda x, y: x | (1 << (y - 1)), e, 0) for e in s]
result = 0
for i in range(2 ** n):
  for j in range(m):
    if (bin(i & t[j]).count('1') & 1) != p[j]:
      break
  else:
    result += 1
print(result)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

#m switch
#n light

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

x=np.array([[0]*m for i in range(n)])

for i in range(n):
	tmp=list(map(int,input().split()))
	for j in range(1,tmp[0]+1):
		x[i][tmp[j]-1]=1

y=list(map(int,input().split()))        
      
s=[0,1]
sw=list(itertools.product(s, repeat=m))

cnt=0

for i in range(len(sw)):
	z=x.dot(np.array(sw[i]).T)
	for j in range(n):
		if z[j]%2!=y[j]:
			break
		if j==n-1:
			cnt+=1
    
print(cnt)