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 numpy as np


def main():
    N, M = map(int, input().split())
    S = []
    for m in range(M):
        S.append([int(s) for s in input().split()][1:])
    P = [int(p) for p in input().split()]

    def f(l):
        a = []
        for e in l:
            a.append(e + [0])
            a.append(e + [1])
        return a

    a = [[0], [1]]
    for n in range(N-1):
        a = f(a)

    count = 0
    for e in a:
        mat = np.zeros((N, M), dtype=np.int)
        mat += np.array(e)[:, None]
        for i in range(M):
            for j in range(N):
                if j+1 not in S[i]:
                    mat[j, i] = 0
        ans = mat.sum(axis=0) % 2
        all_ok = True
        for i in range(M):
            if ans[i] != P[i]:
                all_ok = False

        if all_ok:
            count += 1

    print(count)


main()

Submission status: Accepted

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


S=[0 for i in range(N)]
A=[]

for x in range(M):
    s=list(map(int,input().split()))
    X=[]
    for y in range(1,s[0]+1):
        X.append(s[y])
    A.append(X)
P=list(map(int,input().split()))
#print(A)
ANS=0
for i in range(2**N):
    n=i
    for j in range(N):
        if n//(2**(N-1-j))==1:
            S[j]=1
        else:
            S[j]=0
        n%=(2**(N-1-j))
    #print(S,i)
    cnt=0
    for a in range(M):
        Y=0
        for b in range(len(A[a])):
            Y+=S[A[a][b]-1]
        if Y%2==P[a]:
            cnt+=1
        
    #print(cnt)
    if cnt==M:
        ANS+=1
print(ANS)

Submission status: Accepted

Solution code:
import math 

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 i in range(2**N):
    i_bin = bin(i)[2:]
    i_bin = (N - len(i_bin))*'0' + i_bin
    flag = True
    for m in range(M):
        cnt = 0
        for n in range(N):
            if i_bin[n]=='1' and n+1 in S[m]:
                cnt += 1
        if cnt%2 != P[m]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

n, m = [ int(v) for v in input().split() ]
switch_list = []
for i in range(m):
	switch_list.append([ int(v)-1 for v in input().split() ][1:])
p_list = [ int(v) for v in input().split() ]


def switch_check(inlist):
	ans = 0
	p_list2 = [ [inlist[j] for j in switch_list[i] ].count("1")%2  for i in range(m) ]
	if  p_list2 == p_list:
		ans = 1
	return ans

sumans = 0

for i in range(2**n):
	s = (n-len(bin(i))+2)*"0" +bin(i)[2:]
	sumans  += switch_check(s)

print(sumans)

Submission status: Accepted

Solution code:
import numpy as np

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

ks = []
ss = []
for i in range(m):
    row = list(map(int, input().split()))
    k = row.pop(0)
    ss.append(row)


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

ks = np.array(ks, dtype=np.int64)
ps = np.array(ps, dtype=np.int64)

masks = []
for s in ss:
    mask = sum([2 ** (a - 1)for a in s])
    masks.append(mask)


# 電球iにつながっていて、ONになっているスイッチの個数を2で割ったあまり
def calc_switch_state(i, switch_state):
    num_on = 0
    mask = masks[i]
    switch_state = switch_state & mask
    while switch_state > 0:
        num_on += switch_state % 2
        switch_state //= 2

    return num_on % 2

# i 番目の電球がスイッチの状態sで点灯するかどうか
def is_light_on(i, switch_state):
    return calc_switch_state(i, switch_state) == ps[i]

# 探索
total = 0
for state in range(2**n):
    if all([is_light_on(i, state) for i in range(m)]):
        total += 1

print(total)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    s_num = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if j + 1 in s[k]:
                    s_num[k] += 1
    s_num = [x % 2 for x in s_num]
    if s_num == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

import numpy as np

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

light = []

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

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

result = 0
for i in itertools.product([0, 1], repeat=n):
    i = np.array(i)
    s = 0
    for l in light:
        sel = np.array(l[1:]) - 1
        chk = np.sum(i[sel])
        if chk % 2 != p_list[s]:
            break
        s += 1
    
    if s == m:
        result += 1
            

print(result)

Submission status: Accepted

Solution code:
import numpy as np

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

ks = []
switch_list = [[0 for j in range(10)] for i in range(M)]
for i in range(M):
    ks.append(list(map(int, input().split())))
    for j in range(ks[i][0]):
        switch_list[i][10-ks[i][j+1]] = 1
p = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    flg = True
    binary = format(i, 'b').zfill(10)
    binary = list(map(int, binary))
    for j in range(M):
        on = np.logical_and(switch_list[j], binary)
        total_on = sum(on)
        if total_on%2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

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()))
count = 0
sw = [0] * N

def depth(index):
    global count
    for j in range(M):
        a = 0
        for k in range(ks[j][0]):
            if sw[ks[j][k + 1] - 1] == 1: a += 1
        if a % 2 == P[j]:
            if j + 1 == M: count += 1
        else: break

    for i in range(index, N):
        sw[i] = 1
        depth(i + 1)
        sw[i] = 0

depth(0)
print(count)

Submission status: Accepted

Solution code:
def makelist2(n, m):
    return [[0 for k in range(m)] for i in range(n)]

n, m = map(int, input().split())
switches = makelist2(n,m)
for i in range(m):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)-1):
        switches[tmp[j+1]-1][i] = 1

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

ans = 0
for i in range(pow(2,n)):
    frag = True
    target = "{:0>{}b}".format(i, n)
    for j in range(m):
        kosuu = 0
        for k in range(n):
            if(target[k]=="1"):
                if(switches[k][j]==1):
                    kosuu += 1
        if(kosuu%2 != p[j]):
            frag = False
    if(frag):
        ans += 1

print(ans)

Submission status: Accepted

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

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

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


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

    for pi, s in zip(p, Ss):
        x = pi
        for si in s:
            x ^= ((L & (1 << (si - 1))) != 0) * 1
        if x != 0:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Ss = []
for m in range(M):
    S = list(map(int,input().split()))
    Ss.append(S[1:])
ps = list(map(int,input().split()))
output= []
for i in range(1 << N):
    nums = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            nums.append(1)
        else:
            nums.append(0)
    output.append(nums)
ans = 0
for out in output:
    num = 0
    for (s,p) in zip(Ss,ps):
        count = 0
        for ss in s:
            if out[ss-1]==1:
                count+=1
        if count%2==p:
            num+=1
    if num==len(ps):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, M = map(int, input().split())
S = []
for _ in range(M):
    s = [int(s) for s in input().split()]
    s.pop(0)
    S.append(s)
P = [int(s) for s in input().split()]

ANS = [i for i in range(2**N)]
for p, s in zip(P, S):
    for r in range(p ^ 1, len(s) + 1, 2):
        for selected in combinations(s, r):
            others = set(s) - set(selected)
            n = 0
            for i in selected:
                n += 2**(i - 1)
            m = 0
            for i in others:
                m += 2**(i - 1)
            ANS = [ans for ans in ANS if not (ans & n == n and ans & m == 0)]
print(len(ANS))

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


def convert(nums):
    # print('conv', [2**i for i in nums])
    return sum([2**i for i in nums])


def is_on(ons, bulb, p):
    return bin(ons & bulb).count('1') % 2 == p

def is_all_on(ons, bulbs, ps):
    res = True
    for bulb, p in zip(bulbs, ps):
        # print(ons, bulb, is_on(ons, bulb, p))
        res &= is_on(ons, bulb, p)
    return res


n, m = LI()
k, s = [], []
for _ in range(m):
    _input = LI_()
    s.append(convert(_input[1:]))
    # print('s', _input[1:])

p = LI()

res = 0
for ons in range(2**n):
    res += is_all_on(ons, s, p)

print(res)

Submission status: Accepted

Solution code:
import itertools

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

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

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

switch = [1,0]
comb = []

for x in itertools.product([1,0], repeat=n):
    comb.append(x)
    
c = 0

for i in range(len(comb)):
    light = 0
    
    for j in range(m):
        temp = 0
        for r in range(k[j][0]):
            if comb[i][k[j][r+1]-1] == 1:
                temp += 1
        
        if temp%2 == p[j]:
            light += 1
    
    if light == m:
        c += 1

print(c)

Submission status: Accepted

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

def base(X, a):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%a)+out
        X_dumy = int(X_dumy/a)
    return str(out).rjust(n,'0')
ans=0
for x in range(2**n):
    s=[0 for _ in range(m)]
    b=base(x,2)
    for i in range(m):
        for j in range(ks[i][0]):
            if b[ks[i][j+1]-1]=="0":
                if s[i]==0:
                    s[i]=1
                else:
                    s[i]=0
    if s==p:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def hantei(n,m,s,k,p):
  b = 0
  for l in range(m):
    a = 0
    for x in range(k[l][0]):
      a += s[k[l][x+1]-1]
    if a%2 != p[l]:
      b = 1
  if b == 0:
    return True
  else:
    return False

n,m = map(int,input().split())
k = []
for _ in range(m):
  k.append(list(map(int,input().split())))
p = list(map(int,input().split()))
c = 0
for _ in range(2**n):
  s = [0] * n
  ll = len(bin(_))
  for i in range(ll):
    if i >= 2:
      s[n-ll+i] = int(bin(_)[i])
  if hantei(n,m,s,k,p):
    c += 1
print(c)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
taiou = np.zeros((N,M))
for i in range(M):
    val =  input().split()
    for j in range(int(val[0])):
        v = int(val[j+1])
        taiou[v-1][i] = 1
p = np.array([int(v) for v in input().split()])
cnt = 0
for val in range(2**N):
    v = taiou*np.array([[int(i)] for i in bin(val)[2:].zfill(N)])
    if np.sum(np.sum(v,axis=0)%2==p)==M:
        cnt+=1
    
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
import numpy as np
KS = [np.array(list(map(int, input().split()))) for _ in range(m)]
P = list(map(int, input().split()))

import itertools
cond = np.array([np.array(i) for i in itertools.product([0,1],repeat=n)])

light = 0
for ks,p in zip(KS,P):
  cond = [i for i in cond if sum(i[ks[1:]-1])%2 == p]
  
print(len(cond))

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

isAffectedSwitch=[[False for _ in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(1,s[i][0]+1):
        isAffectedSwitch[i][s[i][j]-1]=True
# print(isAffectedSwitch)
onoff=[[(i%(2**(n-j)))>>(n-j-1) for j in range(n)]for i in range(2**n)]
# print(onoff)
ans=0
for i in range(2**n):
    cnt=[0 for _ in range(m)]
    for j in range(n):
        for k in range(m):
            if onoff[i][j]==1:
                if isAffectedSwitch[k][j]==True:
                    cnt[k]+=1
    isOK=True
    for k in range(m):
        if cnt[k]%2!=p[k]:
            isOK=False
    if isOK:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
# import statistics
import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


n, m = MI()
a = [LI() for _ in range(m)]
p = LI()
index = 0
cnt = 0
for i in range(2 ** n):
    # print("index = "+str(index))
    tento = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            tento[n-1-j] = 1
    index = 0
    for k in a:
        tmp = 0
        for i, num in enumerate(k[1:]):
            if tento[num-1] == 1:
                tmp += 1
        # 条件に当てはまる電球でついてるやつ
        if tmp % 2 == p[index]:
            index += 1
            if index == m:
                cnt += 1
        else:
            break
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
N,M = list(map(int, input().split()))
dat=[]
for i in range(M):
  dat.append(list(map(int, input().split())))
p = list(map(int, input().split()))

A=np.zeros((M,N))
for i in range(M):
  for j in range(len(dat[i])-1):
    A[i,dat[i][j+1]-1]=1
#print(A)
res=0

v = np.zeros((N,1))
for i in range(2**N):
  for j in range(N):
    v[j,0] = int(i / (2**j)) % 2
  w=(np.dot(A,v) % 2)

  flg=True
  for j in range(len(p)):
    if p[j] != int(w[j]):flg=False
  if flg:
    res=res+1
print(res)

Submission status: Accepted

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

count = 0
for i in range(2**n):
  b = format(i, '0%db' % n)
  # print(b)
  judge = True
  for j in range(m):
    if not judge:
      break
    t = 0
    for k in range(1, 1+ks[j][0]):
      idx = ks[j][k] - 1
      if b[idx] == '1':
        t += 1
    if t % 2 != p[j]:
      judge = False
  if judge:
    count += 1
print(count)

Submission status: Accepted

Solution code:
# coding; utf-8
def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for i in range(M):
        temp = list(map(int, input().split()))
        ki = int(temp[0])
        K.append(ki)
        si = list(temp[1:])
        S.append(si)

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

    ans = 0
    temp = [0] * N
    ans += method(temp, N, M, K, S, P, 0)
    print(ans)


def method(l, N, M, K, S, P, roop):
    ans = 0
    if roop < N:
        l[roop] = 0
        ans += method(l, N, M, K, S, P, roop+1)
        l[roop] = 1
        ans += method(l, N, M, K, S, P, roop+1)

    elif roop == N:
        flag = True
        # print(l)
        for i in range(M):
            s = 0
            for j in range(K[i]):
                if l[S[i][j]-1] > 0:
                    s += 1
            if s % 2 != P[i]:
                # print(s, P[i])
                flag = False
        if flag == True:
            ans += 1
        return ans
    else:
        # print("debug")
        return -99
    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ABC128-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
S=[]
for i in range(m):
    t=IL()
    S.append(t[1:])
P=IL()
ans=0
for i in range(pow(2,n)):
    ok=True
    sl=bin(i)[2:].zfill(n)
    for i in range(m):
        w=0
        for idx in S[i]:
            if sl[idx-1]=="1":
                w+=1
        if w%2!=P[i]:
            ok=False
    if ok:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def honyaku(i,N):
    ans = []
    tmp = i
    for i in range(1,N+1):
        ans.append(tmp%2)
        tmp = tmp//2
    return ans
def check(s_list,d_list,p):
    tmp = 0
    for i in range(1,len(d_list)):
        if s_list[d_list[i]-1] == 1:
            tmp += 1
    if tmp%2 == p:
        return True
    else:
        return False

[N,M] = list(map(int,input().split()))
s = []
for i in range(M):
    s_tmp = list(map(int,input().split()))
    s.append(s_tmp)
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    s_list = honyaku(i,N)
    ans_tmp = 0
    for j in range(M):
        if check(s_list,s[j],p[j]) == True:
            ans_tmp += 1
    if ans_tmp == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
L = []
ans = 0
for i in tmp:
    c = 0
    for j in range(1, i[0] + 1):
        c += 2 ** (i[j] - 1)
    L.append(c)

for i in range(2 ** N):
    for j in range(M):
        if not p[j] == bin(L[j] & i).count("1") % 2:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=0
k=[]
def func(n,s,i):
    global ans
    if n==0:
        c=0
        for j in range(m):
            cnt=0
            for a in range(1,len(k[j])):
                if s[k[j][a]-1]==1:
                    cnt+=1
            if cnt%2==p[j]:
                c+=1
        if c==m:
            ans=ans+1
    else:
        for j in range(2):
            if j==0:
                s[i-1]=0
                func(n-1,s,i+1)
            else:
                s[i-1]=1
                func(n-1,s,i+1)

for i in range(m):
    K=list(map(int,input().split()))
    k.append(K)
p=list(map(int,input().split()))
func(n,[0]*n,0)
print(ans)

Submission status: Accepted

Solution code:
N, M = list(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 i in range(2 ** N):
    f = 0
    for j in range(M):
        cc = 0
        for k in range(1, len(s[j])):
            if (i >> (s[j][k] - 1)) % 2 == 1:
                cc += 1
        if cc % 2 != p[j]:
            f = 1
            break
    if f == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().rstrip().split())
k_s = [list(map(int, input().rstrip().split())) for _ in range(M)]
for i in range(M):
    k_s[i].pop(0)
P = list(map(int, input().split()))
#on=1,off=0
count = 0
counter = 0
limit = 2**N
for i in range(2):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for m in range(2):
                    for n in range(2):
                        for o in range(2):
                            for p in range(2):
                                for q in range(2):
                                    for r in range(2):
                                        counter += 1
                                        stats = [r,q,p,o,n,m,l,k,j,i]
                                        flg = True
                                        index = 0
                                        for s in k_s:
                                            sums = 0
                                            for t in s:
                                                sums += stats[t-1]
                                            rem = sums % 2
                                            if rem != P[index]:
                                                flg = False
                                                break
                                            index += 1
                                        if flg:
                                            count += 1
                                        if limit == counter:
                                            print(count)

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
N,M=I()
sw=[]
for _ in [0]*M:
    _,*s=I()
    sw+=[s]
*p,=I()
r=0
for i in range(2**N):
    k=str(bin(i))[2:].rjust(N,"0")
    f=True
    for j in range(M):
        t=0
        for s in sw[j]:
            if k[s-1]=="1":t+=1
        if t%2!=p[j]:f=False;break
    if f:r+=1
print(r)

Submission status: Accepted

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

n = 0
for i in range(2**N):
    nums = [True if n&j != 0 else False for j in [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200]]
    n += 1

    for idx, s_ in enumerate(s):
        x = 0
        for _ in s_[1:]:
            x += nums[_-1]
        if x % 2 != p[idx]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

N, M = [int(_) for _ in input().split()]

k_lis = []

for m in range(M):
  sw =  [int(_) - 1 for _ in input().split()][1:]

  k_lis.append(sw)

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

on_off = [[0], [1]]
tmp = []

for j in range(N-1):
  for t in on_off:
    tmp.append(t + [0])
    tmp.append(t + [1])
  on_off = tmp
  tmp = []

solved = 0
  
for t in on_off:
  flag = True
  for m in range(M):
    total = 0
    for k in k_lis[m]:
      total += t[k]
    if not total % 2 == p_lis[m]:
      flag = False
      break
  if flag:
    solved += 1
      
print(solved)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
# L = [int(x) for x in input().split()]
N, M = map(int, input().split())

S = [[int(x) for i, x in enumerate(input().split()) if i != 0] for _ in range(M)]
P = [int(x) for x in input().split()]

ans = 0
for i in range(2 ** N):
        flag = True

        for j, s in enumerate(S):
                tmp = 0

                for ss in s:
                        if (i >> (ss - 1)) & 1:
                                tmp += 1
                                tmp %= 2
                
                if tmp != P[j]:
                        flag = False

        if flag:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
ks=list(list(map(int,input().split())) for _ in range(M))
P=list(map(int,input().split()))
L=[0,1]
LL=list(itertools.product(L,repeat=N))
ans=0
sum=[]
msum=0
for I in LL:
    sum=[]
    for J in ks:
        msum=0
        for k in range(1,J[0]+1):
            msum+=I[J[k]-1]
        sum.append(msum)
    if all(sum[i]%2==P[i] for i in range(M)):
        ans+=1
print(ans)

Submission status: Accepted

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

# 電球
k = []
s = []


for i in range(M):
    I = input().split()

    k.append(I.pop(0))
    s.append(list(map(int,I)))


P = list(map(int , input().split()))
status = [0]*N

count = 0

for i in range(2**N):
    flag = True

    binary = i
    for j in range(N):
        status[j] = 1 if (binary % 2 == 1) else 0
        binary = int(binary / 2)

    for j in range(M):
        sum = 0
        for index in s[j]:
            sum = sum + status[index-1]

        if sum % 2 != P[j]:
            flag = False
            break

    if flag:
        count = count + 1


print(count)

Submission status: Accepted

Solution code:
# 2019/05/26
# AtCoder Beginner Contest 128 - C

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

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

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

ans = 0
for i in range(2**n):
    binstr = format(i, "010b")
    binlist = list()
    for j in range(10):
        binlist.append(int(binstr[j]))
    
    # Try This case
    is_on = True
    for x in range(m):
        subt = 0
        for y in range(1, ks[x][0] + 1):
            subt += binlist[10 - ks[x][y]] * 1
        
        if subt % 2 != p[x]:
            is_on = False
            break

    if is_on == True:
        ans += 1

# Output
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

connection = []

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

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

A = [0,1]
all_pt = list(itertools.product(A,repeat=N))

all_cnt = 0


for pt in all_pt:
    for con, on_pt in zip(connection, light_on):
         # 1個ずつ精査
        OK = False
        ON = 0
        for t in con:
            if pt[t-1] == 1:
                ON = ON + 1
        if ON % 2 != on_pt:
            break
        OK = True
    if OK:
        all_cnt += 1

print(all_cnt)

Submission status: Accepted

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

ans =0
for i in range(2**N):
    s_state=[]
    for j in range(N):
        s_state.append(i//(2**j)%2)
    all_green=1
    for j in range(M):
        num_on = 0
        for k in s[j]:
            num_on = num_on+s_state[k-1]
        if num_on%2 == p[j]:
            pass
        else:
            all_green=0
            break
    ans = ans + all_green
print(ans)

Submission status: Accepted

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

ptn = []
for i in range(2 ** N):
    ptn.append(list(str(bin(i))[2:].zfill(N)))

ans = 0
for x in ptn:
    sucflg = True
    for oidx,outval in enumerate(li):
        cnt = 0
        for idx,inval in enumerate(outval):
            if idx == 0:
                continue
            if x[inval - 1] == '1':
                cnt += 1
        else:
            if cnt % 2 != p[oidx]:
                sucflg = False
                break
    else:
        if sucflg:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
C = 0
for x in range(2**N):
    X = [x// (2**n) % 2 for n in range(N)]
    X = np.array(X)
    c = 0
    for m in range(M):
        l = np.array(K[m])-1
        if sum(X[l]) % 2 == P[m]:
            c += 1
    if c == M:
        C += 1
print(C)

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,M = list(map(int, input().split()))
        KS = np.zeros((M,N+1),dtype=int)
        for i in range(M):
            tmp = list(map(int, input().split()))
            tmp = tmp + [0]*(N-tmp[0])
            KS[i] = tmp
        P = list(map(int, input().split()))
    else:
        pass
    count = 0
    for i in range(2**N):
        b = "0"*N + bin(i)[2:] 
        tcount = 0
        for j in range(M):
            p = P[j]
            ks = KS[j][1:]
            n = 0
            for tks in ks:
                n += int(b[-tks])
            if n % 2 == p:
                tcount += 1
            else:
                break
        else:
            count += 1
            #print(i,b)

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

Submission status: Accepted

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

switch_conbs = []
for i in range(2 ** N):
    conb = bin(i)[2:].zfill(N)
    switch_conbs.append(list(map(int, list(conb))))

for i, light in enumerate(lights):
    temp = []
    for switch_conb in switch_conbs:
        s = 0
        for v in light[1:]:
            s += switch_conb[v - 1]
        if s % 2 != p_values[i]:
            temp.append(switch_conb)
    
    for l in temp:
        switch_conbs.pop(switch_conbs.index(l))

print(len(switch_conbs))

Submission status: Accepted

Solution code:
import numpy as np
k = []
s = []
N, M = map(int, input().split())
for i in range(M):
    ki, *si = map(int, input().split())
    k.append(ki)
    s.append(si)
p = list(map(int, input().split()))

switch = []
for i in range(2**N):
    switch.append([0] + list(map(int, format(i, 'b').zfill(N)))[::-1])
switch = np.array(switch)

index = set()
for i, (ki, si) in enumerate(zip(k, s)):
    on = []
    for ind, state in enumerate(switch):
        if sum(state[si]) % 2 == p[i]:
            on.append(ind)
    if i == 0:
        index = set(on)
    else:
        index = index & set(on)
print(len(index))