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

# ON/OFF全パターンの配列をつくる
switches = [[] for i in range(pow(2,n))]
for index in range(n):
    div =  pow(2,index)
    for i in range(pow(2,n)):
        term = i // div
        if term % 2 ==0:
            switches[i].append(0)
        else:
            switches[i].append(1)

# 電球につながったスイッチリスト読み込み
light_switch = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    tmp.pop(0)
    light_switch.append(tmp)

# 条件読み込み
p = list(map(int, input().split()))

pattern_num = 0
for s in switches:
    all_on_flg = True
    # 電球ごとに点灯するかどうかチェック
    for num, light in enumerate(light_switch):
        on_num = 0
        for ls in light:
            if s[ls-1] == 1:
                on_num += 1
        if on_num % 2 != p[num]:
            # 条件に反したら、強制終了
            all_on_flg = False
            break
    if all_on_flg:
        pattern_num += 1
print(pattern_num)

Submission status: Accepted

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

from itertools import product

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

total = 0
for switch in bit:
    for i, m in enumerate(mat):
        ison = 0
        for j in m:
            ison += switch[j] 
        match = ison % 2 == p[i]
        if not match:
            break
    else:
        total += 1
print(total)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
S = []
for i in range(M):
    s = list(map(int, input().split()))
    k = s.pop(0)
    assert len(s) == k
    S.append(s)
P = list(map(int, input().split()))
assert len(P) == M

def on(s, p, onoff):
    return sum(onoff[i - 1] for i in s) % 2 == p

n = 0
for onoff in product(range(2), repeat=N):
    if all(on(s, p, onoff) for s, p in zip(S, P)):
        n += 1

print(n)

Submission status: Accepted

Solution code:
import sys

s = []
num = 0
for line in sys.stdin:
    if int(num) == 0:
        N, M = map(int, line.strip().split(" "))
    elif int(num) < M + 1:
        i = num - 1
        s.append(line.strip().split(" ")[1:])
    else:
        p = line.strip().split(" ")
    num += 1

#print(N, M, s, p)

state_num = pow(2, N)
clear_num = 0

for i in range(state_num):
    states = format(i, 'b').zfill(N)
    #print(states)

    all_on = True
    for j in range(M):
        sws = s[j]
        on_num = 0
        #print(sws)
        for sw in sws:
            #print(sw)
            if states[int(sw)-1] == "1":
                on_num += 1
        #print("ON",on_num)
        if on_num % 2 != int(p[j]):
            all_on = False
        #print(all_on)

    if all_on:
        clear_num += 1

print(clear_num)

Submission status: Accepted

Solution code:
import itertools as itt
#n進m桁のbit列の作成
def bit(n,m):
    bi = list((itt.product([i for i in range(n)],repeat = m)))
    return bi
#入力データの受け取り
N,M = list(map(int,input().split()))
L = [list(map(int,input().split())) for  _ in range(M)]
P = [int(s) for s in input().split()]

ans = 0
petterns = bit(2,N)
for pettern in petterns:#bit列から一つ取り出す
    count = 0
    flag = 1
    for i in range(M): #電球を一つ取り出す
        #点灯しているスイッチをカウント
        count = 0
        for j in range(L[i][0]):#j番目のスイッチを一つ取り出す
            if pettern[L[i][j+1] - 1] == 1:
                count += 1
        if count % 2 != P[i]:
            count = 0
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
K={"K"+str(i+1):list(map(int,input().split())) for i in range(m)}
P=list(map(int,input().split()))
for item in K.keys():
  K[item].pop(0)
#print(K)
#print(P)
l=list(itertools.product([0,1],repeat=n))
#print(l)
c=0
for item in l:
  f=0
  for i in range(m):
    l_s=[item[K["K"+str(i+1)][j]-1] for j in range(len(K["K"+str(i+1)]))]
    if sum(l_s)%2==P[i]:
      f+=1
  if f==m:
    c+=1
print(c)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    k, *s = input().split()
    K.append(int(k))
    S.append([int(si) for si in s])
P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    #このスイッチのonoffの組み合わせの時、すべての電球が点灯するか
    on_switch = [0] * N
    all_lights_on = True
    for j in range(N):
        #j番目のスイッチがon
        if i & (1<<j):
            on_switch[j] = 1
    for l in range(M):
        num_on = 0
        s_connected = S[l]
        for s in s_connected:
            if on_switch[s-1]:
                num_on += 1
        if num_on % 2 != P[l]:
            all_lights_on = False
    if all_lights_on:
    	ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

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

b_li = []
for item in li:
    tmp = item.split()[1:]
    cond = 0
    for elm in list(map(int, tmp)):
        cond = cond | (2 ** (elm - 1))
    b_li.append(cond)

cnt = 0
for i in range(2**n):
    for j in range(m):
        k =bin(i & b_li[j])
        onCnt = str(k).count('1')
        if (onCnt % 2) != conds[j]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import product

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()))
    
ans = 0
for comp in product(range(2), repeat=N):
    onoff = [0]*M
    for li in range(M):
        s_on = 0
        for si in range(ks[li][0]):
            s_on += comp[ks[li][si+1]-1]
        
        if s_on%2 == p[li]:
            onoff[li] = 1
    if sum(onoff) == M:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
int_switch_repr = 2**N
light_bulbs_switches = []
for i in range(M):
  k_s = [int(x) for x in input().split()]
  k_i = k_s[0]
  light_bulbs_switches.append(k_s[1:]) # i-th light bulb
P = [int(x) for x in input().split()]  # p_i

ans = 0
for itg in range(int_switch_repr):
  binary_switch_repr = "{w:{fill}{width}b}".format(w=itg, fill='0', width=N)
  all_on = True
  for lbs_i, p_i in zip(light_bulbs_switches, P):
    is_light_on = sum([1 for sw in lbs_i if binary_switch_repr[int(sw)-1]=='1'])%2 == p_i
    if not is_light_on:
      all_on = False
      break
  if all_on:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
int_switch_repr = 2**N
light_bulbs_switches = []
for i in range(M):
  k_s = [int(x) for x in input().split()]
  k_i = k_s[0]
  light_bulbs_switches.append(k_s[1:]) # i-th light bulb
P = [int(x) for x in input().split()]  # p_i

ans = 0
for itg in range(int_switch_repr):
  binary_switch_repr = "{w:{fill}{width}b}".format(w=itg, fill='0', width=N)
  all_on = True
  for lbs_i, p_i in zip(light_bulbs_switches, P):
    is_light_on = sum([1 for sw in lbs_i if binary_switch_repr[int(sw)-1]=='1'])%2 == p_i
    if not is_light_on:
      all_on = False
  if all_on:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    b = [int(i) for i in input().split()]
    s.append(b[1:])
p=[int(i) for i in input().split()]
ans=0
for i in range(2**n):
    s_ind=0
    k=bin(i)[2:]
    k=k.zfill(n)
    for j in s:
        c=0
        for M in j:
            if k[-M]=="1":c+=1
        if p[s_ind]!=c%2:break
        s_ind += 1
        if s[-1]==j:
            ans+=1
print(ans)

Submission status: Accepted

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

# 指定された電球(sたち)が全部付いているときを10進数にしてリスト
s = []
for i in ks :
        t = 0
        for j in range(len(i)) :
                t += 2**(n-i[j])
        s.append(t)

# 2**nまでの二進数の中で電球１がつくやつ→電球２がつく→・・・最後まで満たしたら1を足す。を繰り返す
ans = 0
for i in range(2**n) :
        flag = True
        for j in range(m) :
                if bin(s[j] & i).count('1') % 2 != p[j] :
                        flag = False
                        break
        if flag :
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
KS = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
p = [int(x) for x in stdin.readline().rstrip().split()]

k = [KS[l][0] for l in range(M)]
s = [KS[m][1:] for m in range(M)]
cnt = 0


def to_binary(x):
    out = ''
    for l in range(N):
        if x >= 2 ** (N - l - 1):
            out += '1'
            x -= 2 ** (N - l - 1)
        else:
            out += '0'
    return out


for m in range(2 ** N):
    bin_num = to_binary(m)
    for x in range(M):
        swi = 0
        for y in range(k[x]):
            if bin_num[s[x][y] - 1] == '1':
                swi += 1
        if swi % 2 != p[x]:
            break
        if x == M - 1:
            cnt += 1

print(cnt)

Submission status: Accepted

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


for i in range(2**n):
  b = bin(i)[2:].rjust(n, '0')
  light = list(str(b))
  for l, j in enumerate(li):
    num_swith = j[0]
    count = 0
    for k in j[1:]:
      count += int(light[k-1])
    if count % 2 != zero_one[l]:
      break
      
    if l == m-1:
      all_count += 1
      
      
print(all_count)

Submission status: Accepted

Solution code:
#入力部
N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0
#print('s= ', s)
#print('p= ', p)


#すべてのスイッチの状態の組み合わせに対するfor
for i in range(2 ** N):
  ptn = bin(i)[2:].rjust(N, "0")  #スイッチの状態の組み合わせを全表示
  light = True  #フラグ
#  すべての電球に対するfor
  for j in range(M):
    tmp = 0  # スイッチOnに対するカウンター
    #電球が接続しているスイッチの数に対するfor
    for n in range(1, s[j][0] + 1):
      if ptn[s[j][n] - 1] == "1": #点灯状態の確認
        tmp += 1
    if tmp%2 != p[j]%2:
      light = False
  if light:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
N, M = [int(x) for x in stdin.readline().rstrip().split()]
K = []
S = []
for i in range(M):
    k, *s = map(int, input().split())
    K.append(k)
    S.append(s)
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
for n in list(itertools.product([0,1],repeat=N)):
    flag = True
    for ind,s in enumerate(S):
        fired = 0
        for s_index in s:
            if n[s_index - 1] == 1:
                fired += 1
        if fired % 2 != P[ind]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
n_switch = []
switch = []
for i in range(M):
	s = list(map(int, input().split()))
	n_switch.append(s[0])
	switch.append(s[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
	x = 1
	b = bin(i)[2:].rjust(N, '0')
	for j in range(M):
		n_light = 0
		for k in range(n_switch[j]):
			if b[switch[j][k] - 1] == '1':
				n_light += 1
		if n_light % 2 != p[j]:
			x *= 0
			break
	if x == 1:
		ans += 1
print(ans)

Submission status: Accepted

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

n_switches = []
switches = []
for i in range(M):
    ipt = list(map(int, input().split()))
    n_switches.append(int(ipt[0]))
    switches.append(ipt[1:])


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

ans = 0

# print(n_switches)
# print(switches)
# print(p)

# ランプの光り方のパターンだけ
for i in range(2 ** N):
    ptn = bin(i)[2:].rjust(N, '0')

    allLight = True  # 全ての電球が光っているかどうか（一つでも光っていなければそのパターンは無効）

    # 電球の数だけ
    for j in range(M):

        n_light = 0
        # 電球に対するスウィッチの数だけ
        for k in range(n_switches[j]):
            # スウィッチが光っていれば
            if ptn[switches[j][k] - 1] == '1':
                n_light += 1

        if n_light % 2 != p[j]:
            allLight = False
            break

    if allLight:
        ans += 1

print(ans)

Submission status: Accepted

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

c = 0
for n in range(1 << N):
    for i, S in enumerate(A):
        #print(P[i] , sum(n >> s-1 & 1 for s in S))
        if P[i] ^ sum(n >> s-1 & 1 for s in S) & 1:
            break
    else:
        c += 1

print(c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
bulbs = []
for i in range(M):
    l = list(map(int,input().split()))
    bulbs.append(l)
p = list(map(int,input().split()))

ans = 0
for i in range(2 ** N):
    switches = []
    for j in range(N):
        if (i >> j) & 1:
            switches.append(1)
        else:
            switches.append(0)
    
    #print(switches)
    #条件を満たすかどうか調べる
    flag = True
    for x in range(M):
        count = 0
        k = bulbs[x][0]
        for y in range(1, k + 1):
            if switches[bulbs[x][y] - 1] == 1:
                count += 1
        if (count % 2) != p[x]:
            flag = False
            break
    
    if flag == True:
        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
for b in range(1<<N): #スイッチon offの全ての状態を列挙
  for i in range(M): # M個の電球に対して
    c = 0
    for s in src[i][1: ]: # つながっているそれぞれのスイッチが
      if b&(1<<(s-1)): # onになっているかどうか
        c += 1 # onになっていればcountを+1
    if c%2 != P[i]: break # countの偶奇を判定して、一致しなければ次の電球を調べる
  else: # そうでなければans+=1
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

#n桁のm値のbitを生成
def bit(n, m):
    bit_list = list(itertools.product([i for i in range(m)], repeat=n))
    return bit_list

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

patterns = bit(N, 2)

res = 0
for pattern in patterns:
    flag = True
    
    for i in range(M):
        count = 0
        
        for j in range(L[i][0]):
            if pattern[L[i][j+1] - 1] == 1:
                count += 1
                
        if count%2 != P[i]:
            flag = False
            
    if flag:
        res += 1
        
print(res)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import add
n, m = [int(i) for i in input().split()]

lamp = [None] * m
for i in range(m):
    tmp = ['0'] * n
    for k in [int(j) for j in input().split()][1:]:
        tmp[n-k] = '1'
    lamp[i] = int(''.join(tmp), 2)

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

ans = 0
for i in range(0, 2**n):
    if all([bin(i & lamp[j]).count("1") % 2 == p[j] for j in range(m)]):
        ans += 1

print(ans)

Submission status: Accepted

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

def mask(l):
    m = 0
    for i in l:
        m += 2**(i-1)
    return m

masks = list(map(mask, sw))

ret = 0
for i in range(2**N):
    if all(bin(i&m).count('1')%2 == p for m, p in zip(masks, P)):
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
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( 1 << N):
    t = [0]*M
    for j in range(N):
        if ((i >> j) & 1) == 1:
            for x in range(M):
                for y in range(k[x][0]):
                    if k[x][y+1] == j+1:
                        t[x] += 1
    c = 0
    for q in range(M):
        if t[q] % 2 == p[q]:
            c += 1
    if c == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
S = [[0]*(N+1) for _ in range(M)]
for i in range(M):
    k, *s = rl()
    for s_ in s:
        S[i][s_] = 1
P=rl()

ans = 0
import itertools
for switch in itertools.product(range(2),repeat=N):
    ret = 0
    for p, s in zip(P,S):
        cnt = 0
        for i in range(N):
            cnt += switch[i]*s[i+1]
        if p != cnt%2:
            break
        ret += 1
    ans += ret//M

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, raw_input().split())
data = [map(int, raw_input().split()) for i in range(M)]
p = map(int, raw_input().split())
k = [data[i][0] for i in range(M)]
s = [data[i][1:] for i in range(M)]

candidate = []

def Check(switches):
    for i in range(M):
        if (sum([switches[s[i][j] - 1] for j in range(k[i])]) % 2) != p[i]:
            return 0
    return 1

print sum(Check(switches) for switches in itertools.product([0, 1], repeat=N))

Submission status: Accepted

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            tmp = matrix[pivot, :].copy()
            matrix[pivot, :] = matrix[rank, :]
            matrix[rank, :] = tmp

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] - matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Accepted

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            tmp = matrix[pivot, :].copy()
            matrix[pivot, :] = matrix[rank, :]
            matrix[rank, :] = tmp

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] + matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Accepted

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix, is_extended=False):
        num_row = matrix.shape[0]
        num_col = matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # if is_extended and col == num_col - 1:
            #     break

            pivot = -1
            ma = 0
            for row in range(rank, num_row):
                if matrix[row][col] > ma:
                    ma = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue

            tmp = matrix[pivot, :].copy()
            matrix[pivot, :] = matrix[rank, :]
            matrix[rank, :] = tmp

            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] + matrix[rank][col2]) % 2
            rank += 1
        return rank

    a = np.zeros((M, N), dtype='uint8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Accepted

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

count = 0
for i in range(2**N):
    switch = (("{:0"+str(N)+"b}").format(i))[::-1]
    judge = True
    for m in range(M):
        if sum(int(switch[j-1]) for j in s[m]) % 2 != p[m]:
            judge = False
            break
    if judge:
        count += 1

print(count)

Submission status: Accepted

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

for i in range(2**N):
    bulb=[0]*M
    x=format(i,'b').zfill(N)   # x is switch
    #print('x',x)
    for j in range(M):
        #print('j',j)
        total=0
        for k in range(arr[j][0]):
            #print('arr[j][k+1]',arr[j][k+1])
            #print('x[.]',x[ arr[j][k+1]-1 ])
            #print('total',total)
            total+=int(x[ arr[j][k+1]-1 ])
        if total%2!=p[j]:
            break
        else:
            bulb[j]=1
    if sum(bulb)==M:
        cnt+=1
        #break
print(cnt)

Submission status: Accepted

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

ans=0
Lswitches=[]
for j in range(2**N):
    Lswitches.append(format(j,'b').zfill(N))

for k in Lswitches:
    M_off=0
    for m in range(M):
        n=1
        Even_Odd=0
        while n<=Lks[m][0]:
            if k[Lks[m][n]-1]=="1":
                Even_Odd+=1
            else:
                pass
            n+=1
        if Even_Odd%2!=Lp[m]:
            M_off+=1
        else:
            pass
    if M_off==0:
        ans+=1
    else:
        pass

print(ans)

Submission status: Accepted

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

# 全通り探索すれば良い
# 全スイッチパターンのリストの作成
S = []
def switch(x=[], y=0):
    if y == n:
        return S.append(x)
    for i in range(2):
        switch(x+[i], y+1)
switch()

# 全パターンの探索
ans = 0
for i in S:    # スイッチの状態
    s = 1
    for j in range(m):    # 全ての電球を探索
        # 電球につながるスイッチのon-offリストを作る
        Sk = []
        for k in L[j][1:]:
            Sk.append(i[k-1])
        # onになっているスイッチの個数を2で割った余りがpiに等しい時に点灯
        if Sk.count(1) % 2 == P[j]:
            s *= 1
        else:
            s *= 0
    ans += s

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
switch_idx = [[int(i) for i in input().split()[1:]] for M in range(M)]
p = [int(i) for i in input().split()]

import numpy as np
n_pattern = 2**N
form = '0{0}b'.format(N)
ans = 0
from operator import itemgetter
for i in range(n_pattern):
    state = str(format(i, form))
    counter = 0
    for j,k in enumerate(switch_idx):
        if (itemgetter(*(np.array(k)-1))(state).count('1') % 2) == p[j]:
            counter += 1
        if len(switch_idx) == counter:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from functools import reduce
from itertools import combinations

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def is_MM(s):
    num = int(s)
    return 0 < num <= 12


def solve():
    N, M = il()
    KS = iml(M)
    p = il()

    ans = 0
    for i in range(1 << N):
        for j in range(M):
            swi = 0
            for s in KS[j][1:]:
                swi += 2 ** (s - 1)
            if (bin(i & swi).count("1") % 2) != p[j]:
                break
        else:
            ans += 1
    return ans


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

for i in range(2**N):#switch loop
    for j in range(M):#num of light
        sw_see=0
        for k in ks[j][1:]:#switch to see
            sw_see+=2**(k-1)
        if (bin(i&sw_see)).count('1')%2!=p[j]:
            break
    else:
        ans+=1

print(ans)

Submission status: Accepted

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

for i in range(2**N):
    for j in range(M):
        switchnum = 0
        for k in switch[j][1:]:
            switchnum += 2**(k-1)
        
        if (bin(i & switchnum).count('1') % 2 != p[j]):
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
count=0
for i in range(m):
  l1=list(map(int,input().split()))
  del l1[0]
  l.append(l1)
lm=list(map(int,input().split()))
for i in range(2**n):
  c2=0
  l2=[]
  for j in range(n):
    if i>=2:
      l2.append(i%2)
      i=i//2
    else:
      l2.append(i)
      i=i//2
  for j in range(m):
    c=0
    for k in range(len(l[j])):
      if l2[l[j][k]-1]==1:
        c+=1
    if c%2==lm[j]:
      c2+=1
  if c2==m:
    count+=1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
s = []

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

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

ans = 0
for value in range(1 << n):
    all = True
    for i in range(m):
        count = 0
        for j in range(1, s[i][0] + 1):
            count += ((1 << (s[i][j] - 1)) & value) != 0
        if count % 2 != p[i]:
            all = False
            break
    if all:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[]
for i in range(M):
    s.append(list(map(int,input().split())))
p=list(map(int,input().split()))
count=0
for state in range(1<<N):
    flag = 0
    for i in range(M):
        count_ = 0
        flag=1
        for j in range(1, s[i][0]+1):
            if (1 << (s[i][j] - 1)) & state:
                count_ += 1
        if count_ % 2 != p[i]:
            flag = 0
            break
    if flag:
        count += 1
print(count)