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 sys


def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass

        if dec % 2 == p[x]:
            pass
        else:
            return 0

    return 1


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

    k = [0] * M
    s = [0] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())


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

    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
s = []
for _ in range(m):
    s.append(na()[1:])
p = na()
ans = 0
for switch in itertools.product([0,1], repeat=n):
    flag = True
    for si, pi in zip(s, p):
        c = sum(switch[i-1] for i in si)
        if c % 2 != pi:
            flag = False
            break
    if flag == True:
        ans += 1
print(ans)

Submission status: Accepted

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

for x in range(2**N):
  bin_str = format(x, '0{0}b'.format(N))
  X=np.array(list(map(int,list(bin_str))))
  flg=True
  for i in range(M):
    if sum(X[np.array(ks[i][1:])-1])%2 != p[i]:
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
res=0
for i in range(2**n):
    b=list(str(bin(i))[2:].zfill(n))
    #print(b)
    my=True
    for j in range(m):
        pre=0
        for k in range(a[j][0]):
            #print(pre,a[j][k+1],b,b,b[a[j][k+1]-1])
            pre+=int(b[a[j][k+1]-1])
        if p[j]==0:
            if pre%2!=0:
                my=False
        else:
            if pre%2!=1:
                my=False
        #print(b,pre,my,j)
    #print(b,pre,my)
    if my:
        #print(b)
        res+=1
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lamp_list = []
for j in range(M):
  lamp_list.append([i-1 for i in map(int,input().split())])
  lamp_list[j].pop(0)
mod_list = [i for i in map(int,input().split())]

ans = 0

for i in range(2**N):
  sum_list = [0 for i in range(M)] # ランプに接続されたスイッチのon合計
  for j in range(N):
    if ((i>>j)&1):
      for k in range(M):
        if j in lamp_list[k]:
          sum_list[k] += 1
  ok = 1
  for k in range(M):
    if sum_list[k]%2 != mod_list[k]:
      ok = 0
  if ok:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
def cntBit(n):
    cnt = 0
    while n > 0:
        cnt += (n & 1)
        n >>= 1
    return cnt


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

switch = [list(map(int, input().split())) for _ in range(M)]
B = []
for K, *S in switch:
    b = 0
    for k in range(K):
        b += (1 << (S[k] - 1))
    B.append(b)
P = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    on = True
    B1 = list(map(lambda x: x & i, B))
    B2 = list(map(cntBit, B1))
    B3 = list(map(lambda x: x % 2, B2))

    if B3 == P:
        ans += 1

print(ans)

Submission status: Accepted

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

switch = [list(map(int, input().split())) for _ in range(M)]
B = []
for K, *S in switch:
    b = 0
    for k in range(K):
        b += (1 << (S[k] - 1))
    B.append(b)

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

ans = 0
for i in range(2 ** N):
    on = True
    for j, b in enumerate(B):
        cnt = 0
        state = b & i
        while state > 0:
            cnt += state & 1
            state >>= 1
        on &= (cnt % 2 == P[j])
    ans += on

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    S.append(tmp[1:])
P = list(map(int, input().split()))
ans = 0
# print(S)
for bit in range(2**N):
    l = []
    for j in range(N):
        if bit >> j & 1 == 1:
            l.append(1)
        else:
            l.append(0)
    flag = True
    for j in range(M):
        t = S[j]
        cnt = 0
        for k in range(len(S[j])):
            if l[t[k]-1] == 1:
                cnt += 1
            # else:
            #     flag = False
        if cnt % 2 != P[j]:
            flag = False
    if flag:
        # print(bin(bit))
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 始点を0にするため1を引く
# kを除くために[1:]
connected_switches = [[int(i) - 1 for i in input().split()[1:]]
                      for _ in range(M)]
ps = list(map(int, input().split()))

# https://atcoder.jp/contests/abc128/submissions/9251177 がとてもわかりやすいので参考にする

ans = 0
# どのスイッチがONになっているかの全パターン
for bit in range(2 ** N):
    ok = True
    # 各電球について回す、これは電球個（M個）あるpsが全て条件を満たしているかを確認するため
    for i in range(M):
        # i番目の電球に繋がっている、状態onのスイッチ個数
        connected_on_num = 0
        for s in connected_switches[i]:
            # 今確認しているパターン（bit）で
            # i番目の電球に繋がっているスイッチsがonとなる場合
            # 例: Nが4、bitが3
            # 0番目: ON
            # 1番目: ON
            # 2番目: OFF
            # 3番目: OFF
            # となるケースで、forで回しているs（i番目の電球に繋がっているスイッチ）が
            # 0番目もしくは1番目のとき、connected_numを加算
            if bit & (1 << s):
                connected_on_num += 1
        if connected_on_num % 2 != ps[i]:
            ok = False
            break
    # 今確認しているパターン（bit）で
    # すべての電球が点灯している場合（connected_on_num % 2 != ps[i] が全てFalseだった場合）
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0
    for switch in range(2**N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                if switch >> (b - 1) & 1:
                    cnt += 1

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans


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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    s=[None]*n
    for j in range(n):
        if (i>>j)&1:
            s[j]=True
        else:
            s[j]=False
    total=0
    for y,k in enumerate(a):
        cnt=0
        for x,l in enumerate(k):
            if x==0:
                continue
            if s[l-1]==True:
                cnt+=1
        if cnt%2==p[y]:
            total+=1
    if total==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = [int(x) for x in input().split()]
    k = []
    s = []
    for i in range(m):
        input_arr = [int(x) for x in input().split()]
        # print(input_arr[0])
        k.append(input_arr[0])
        # print(input_arr[1:])
        s.append(input_arr[1:])

    p = [int(x) for x in input().split()]
    # print()
    ans = 0
    for i in range(1 << n):
        cnt = 0
        for l in range(m):
            cc = 0
            for j in range(k[l]):
                ss = s[l][j]-1
                # print(l, ss)
                if i & (1 << ss):
                    cc ^= 1
            if cc == p[l]:
                # print(l+1)
                cnt += 1
        if cnt == m:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

p=list(map(int,input().split()))
ans=0
for s in range(2**n):#switchの組み合わせ
    s=format(s,'b')
    s=s.zfill(n)
    s=str(s)
    for j in range(m):#各電球について
        sn=0
        for k in range(1,a[j][0]+1):#点灯個数みる
            sn+=int(s[a[j][k]-1])
        if sn%2==p[j]:
            flag=True
        else:
            flag=False
            break
    if flag:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 0
[N,M] = inpl()
bulblist = [None]*M
for i in range(M):
    temp = inpl()
    k = temp[0]
    bulblist[i] = temp[1:]

plist = inpl()

for bit in range(1<<N):
    flag = 1
    for i in range(M):
        numon = 0
        for l in bulblist[i]:
            numon += (bit >> (l-1) & 1)
        if numon % 2 != plist[i]: flag = 0
    if flag: ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for node in list(itertools.product([0,1], repeat=N)):
  # 各組み合わせで試す ON:1, OFF:0
  ans_a = 0
  for i in range(M):
    # 各条件に当てはまっているか試す
    k = k_list[i]
    cnt = 0
    for j in range(k[0]):
      # スイッチがOnの個数を数える
      cnt += node[k[j+1]-1]
    if cnt % 2 == p_list[i]:
      ans_a += 1
  if ans_a == M:
    ans += 1
      
print(ans)

Submission status: Accepted

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

a = [0] * N
for i in range(M):
    K, *S = list(map(int, input().split()))
    for j in range(K):
        s = S[j]
        s -= 1
        # s番目のスイッチにi番目の電球が繋がっている
        a[s] |= 1 << i

expected = 0
P = list(map(int, input().split()))
for i in range(M):
    if P[i]:
        expected |= 1 << i

ans = 0
for s in range(1 << N):  # スイッチの状態
    tmp = 0
    for i in range(N):
        if s >> i & 1:
            tmp ^= a[i]
    if tmp == expected:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(m):
    s[i].pop(0)

#print(s)
for i in range(2**n):
    tmp = [False] * m
    #print(bin(i))
    for j in range(n):
        if (i>>j) & 1:
            for k in range(m):
                if (j+1) in s[k]:
                    tmp[k] = not tmp[k]
    #print(tmp,p,tmp == p)
    if tmp == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = {} # int -> list[int]

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

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


def check(a, b):
    swithes = d[a]
    characteristic = p[a]
    s = 0

    for i in range(n):
        if (b >> i) % 2 == 1:
            if n-i in swithes:
                s += 1

    return True if s % 2 == characteristic else False


count = 0

for i in range(1 << n):
    for j in range(m):
        if check(j, i):
            if j == m-1:
                count += 1
        else:
            break

print(count)

Submission status: Accepted

Solution code:
import itertools


n, m = [int(i) for i in input().split()]
light = []
light_append = light.append
for _ in range(m):
    light_append([int(i) - 1 for i in input().split()][1:])
p = [int(i) for i in input().split()]

ans = 0
for bit in itertools.product((0, 1), repeat=n):
    for i, l in enumerate(light):
        if sum([bit[j] for j in l]) % 2 != p[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
K = []
S = []
for _ in range(M):
    k, *s = [int(i)-1 for i in input().split()]
    K.append(k)
    S.append(set(s))

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


res = 0
for bit in range(2**N):
    ok = True
    for i in range(M):
        c = 0
        for v in S[i]:
            if bit & (2**v):
                c += 1
        if c % 2 != P[i]:
            ok = False
    if ok:
        res += 1

print(res)

Submission status: Accepted

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

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

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

# print(s)

def isAllOn(n):
    # print('\nn:', n)
    for i in range(m):
        # print('Light:', i)
        bitCnt = 0
        for j in range(len(s[i])):
            pos = s[i][j] - 1
            # print('pos:', pos)
            bit = (n >> pos) & 1
            if bit == 1:
                bitCnt += 1
        if bitCnt % 2 != p[i]:
            # print('False!')
            return False

    return True

ans = 0

for i in range(2**n):
    if isAllOn(i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for swith in product(*[(True, False) for _ in range(N)]):
    for i in range(M):
        if sum(int(s) for j, s in enumerate(swith, 1) if j in S[i]) % 2 != P[i]:
            break
    else:
        ans += 1
print(ans)

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

C = [format(i, "0" + str(n) + "b") for i in range(2**n)]

ans = 0
for c in C:
    l = 0
    for i in range(m):
        o = sum(int(c[s - 1]) for s in S[i])
        if o % 2 == P[i]:
            l += 1
    if l == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools


n, m = map(int, input().split())
KS = []
for _ in range(m):
    ks = list(map(int, input().split()))
    KS.append(ks)
P = list(map(int, input().split()))

C = list(itertools.product((0, 1), repeat = n))

ans = 0
for c in C:
    l = 0
    for i in range(m):
        k = KS[i][0]
        o = 0
        for j in range(k):
            s = KS[i][j + 1]
            o += c[s - 1]
        if o % 2 == P[i]:
            l += 1
    if l == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
sss = []
for i in range(m):
    _, *ss = list(map(int, input().split()))
    sss.append(ss)
ps = list(map(int, input().split()))

ret = 0
for i in range(2 ** n):
    lst = [(i & (2 ** j) == 0) for j in range(n)]

    f = True
    for idx, ss in enumerate(sss):
        cnt = 0
        for s in ss:
            cnt += lst[s - 1]
        if cnt % 2 != ps[idx]:
            f = False
            break

    if f:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for i in range(M):
  ks = list(map(int, input().split()))
  S.append(sum(1<<(s-1) for s in ks[1:]))

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

ans = 0
for state in range(2**N):
  on = True
  for m in range(M):
    on = bin(S[m] & state).count('1') % 2 == p[m]
    if not on:
      break
  
  ans += on

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0

    for switch in range(2**N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                if switch >> (b - 1) & 1:
                    cnt += 1
            if cnt % 2 == P[i]:
                check[i] = 1
        if all(check):
            ans += 1
    return(ans)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
eo = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  sw = [0]*n
  binstr = format(i,"b").zfill(n)
  for j in range(n):
    if binstr[j] == "1":
      sw[j] = 1
  light = 0
  for k,y in enumerate(x):
    numsw = 0
    for z in range(1,y[0]+1):
      if sw[y[z]-1] == 1:
        numsw += 1  
    if numsw%2 == eo[k]:
      light += 1
  if light == m:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

#S[i]は、電球iのスイッチ接続の様子
S = np.array([np.zeros(N,int) for _ in range(M)])
for i in range(M):
    L = list(map(int, input().split()))
    for j in range(L[0]):
        S[i][L[j+1]-1] = 1

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

for i in range(2**N):
    #Bはiの2進数表示
    B = np.zeros(N)
    for j in range(N):
        if (1<<j)&i != 0:
            B[j] = 1
    
    flg = 1
    for j in range(M):
        dot = np.dot(B,S[j])
        if dot%2 != P[j]:
            flg = 0
            break
    
    if flg==1:
        ans += 1

print(ans)

Submission status: Accepted

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

N = [n_i for n_i in range(1, n+1)]
S_all = []

for i in range(2**n):
  s = set()
  for j in range(n):
    if i&(1<<j):
      s.add(N[-j])
  S_all.append(s)

count = 0

for s_i in S_all:
  count_flg = True
  for m_i in range(m):
    if P[m_i]==0 and (len(S[m_i]&s_i))%2==1: count_flg = False
    if P[m_i]==1 and (len(S[m_i]&s_i))%2==0: count_flg = False
  if count_flg:count += 1

print(count)

Submission status: Accepted

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


ans = 0
a = [0] * N
for i in range(1 << N):
    for j in range(N):
        if i >> j & 1 == 1:
            a[j] = 1
        else:
            a[j] = 0
    for j in range(M):
        sc = 0
        for l in range(k[j][0]):
            if a[k[j][l+1]-1] == 1:
                sc += 1
        if sc % 2 != p[j]:
            break
        elif j == M-1:
            ans += 1
            
print(ans)

Submission status: Accepted

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

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

ans=2**N
for i in range(2**N):
  for j in range(M):
    cnt=0
    for k in L[j]:
      cnt+=A[i][k-1]
    if P[j]!=(cnt%2):
      ans-=1
      break
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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

S = []
switch_to_light = defaultdict(list)
for i in range(M):
    s = list(map(int, input().split()))[1:]
    for si in s:
        switch_to_light[si].append(i+1)
p = list(map(int, input().split()))

L = [0, 1]
num = N
bit_list = list(itertools.product(L, repeat=num))

ans = 0
for bits in bit_list:
    lights = [0]*(M+1)
    for i, bit in enumerate(bits):
        s = i+1
        if bit == 0:
            continue
        l = switch_to_light[s]
        for li in l:
            lights[li] += 1
    
    lights = list(map(lambda x:x%2, lights))[1:]
    res = True
    for li, pi in zip(lights, p):
        if li != pi:
            res = False
            break
    if res:
        ans += 1

print(ans)

Submission status: Accepted

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

#ks=[list(map(int,input().split())) for _ in range(M)]
k=[]
s=[]
for i in range(M):
    inp=list(map(int,input().split()))
    k.append(inp[0])
    s.append(inp[1:])

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

fil=1
A=0
for ans in range(2**N):#ONになっている電球の組み合わせをbit全探索
    for i in range(M):#各電球ごと
        sw_on_cnt=0
        for j in range(k[i]):#各電球の指定のスイッチごと k[i]はi番目の電球がswにつながっている数
            if ans>>(s[i][j]-1)&fil==1:#優先順位は-,>>,& sw_numで指定されたswがONなら
                sw_on_cnt+=1
        if sw_on_cnt%2==p[i]:
            pass
        else:
            break
    else:
        A+=1
print(A)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n, m = map(int, input().split())
    s = [tuple(map(int, input().split()[1:])) for _ in range(m)]
    p = tuple(map(int, input().split()))

    c = 0
    f = '0' + str(n) + 'b'
    for i in range(2 ** n):
        xi = 'x' + format(i, f)
        for j in range(m):
            if sum([int(xi[k]) for k in s[j]]) % 2 != p[j]:
                break
        else:
            c += 1
    print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M =map(int,input().split())
L = [list(map(int,input().split()))[1:] for i in range(M)]
p = list(map(int,input().split()))
form = "0" + str(N) + "b"
ans = 0
for i in range(2**N):
    pat = format(i,form)
    flg = True
    for j in range(M):
        s = sum(int(pat[k-1]) for k in L[j])
        if s%2 != p[j]:
            flg = False
    if flg == True:
        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()))[1:])
p = list(map(int, input().split()))
casecnt = 0
for i in range(2**n):
  case = list(map(int, list(("{:0" + str(n) + "b}").format(i))))
  oncnt = 0
  for j in range(m):
    soncnt = 0
    for k in range(len(s[j])):
      soncnt += case[s[j][k]-1]
    if soncnt % 2 == p[j]:
      oncnt += 1
  if oncnt == m:
    casecnt += 1
print(casecnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c
# なんかかすかに解いた記憶あるな？

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


def is_on(i, S, p):
    # bit表現 i のときSのスイッチの個数とpでonか返す
    cnt = 0
    for j in S:
        if (i >> (j - 1)) % 2:  # j番目のスイッチオン
            cnt += 1
    return cnt % 2 == p


ans = 0
# bit 全探索
for i in range(1 << N):  # N桁のbit全探索
    # 以下iの全パターンについて
    flg = True
    for s, p in zip(S, P):
        if not is_on(i, s, p):
            flg = False
            break
    ans += flg
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c
# なんかかすかに解いた記憶あるな？

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


def is_on(i, S, p):
    # bit表現 i のときSのスイッチの個数とpでonか返す
    cnt = 0
    for j in S:
        if (i >> (j - 1)) % 2:  # j番目のスイッチオン
            cnt += 1
    return cnt % 2 == p


ans = 0
# bit 全探索
for i in range(1 << N):  # N桁のbit全探索
    # 以下iの全パターンについて
    flg = True
    for s, p in zip(S, P):
        flg *= is_on(i, s, p)
    ans += flg
print(ans)

Submission status: Accepted

Solution code:
#ABC-128-C
N, M = map(int, input().split())
S = []
ans = 0

for i in range(M):
    ki, *six = map(int, input().split())
    S.append((i, six))

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

for i in range(0, (2**N)):
    confidence = True
    for item in S:
        on_switches = 0
        for switch in item[1]:
            on_switches += i >> (switch-1) & 1
        if on_switches % 2 != P[item[0]]:
            confidence = False
            break
    if confidence == True:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ms = [[] for _ in range(m)]
for eachm in range(m):
    ks = list(map(int, input().split()))
    for i in range(1, ks[0]+1):
        ms[eachm].append(ks[i]-1)
ps = list(map(int, input().split()))
res = 0
for status in range(2 ** n):
    switches = [(status >> bit) % 2 for bit in range(n)]
    num_on = 0
    for eachm in range(m):
        p = ps[eachm]
        for eachs in ms[eachm]:
            p ^= switches[eachs]
        if p == 0:
            num_on += 1
    if num_on  == m:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
s=[]
for i in range(M):
    switch=[]
    k,*switch = map(int,input().split())
    for j in range(len(switch)):
        switch[j]-=1
    s.append(switch)
p=[int(l) for l in input().split()]


count=0
for i in range(1<<N):
    is_ok =True
    for j in range(len(s)):
        c=0
        for k in s[j]:
            if (i>>k)%2==1:
                c+=1
        if c%2==p[j]:
            continue
        else:
            is_ok=False
            break
    if is_ok:
        count+=1

print(count)

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(m):
    inp = [int(i) for i in sys.stdin.readline().split()]
    k = inp[0]
    s_sum = sum([2 ** (i - 1) for i in inp[1:]])
    ls.append(s_sum)
p_ls = [int(i) for i in sys.stdin.readline().split()]
cnt = 0
for i in range(1 << n):
    flg = True
    for p, s in zip(p_ls, ls):
        if sum([int(i) for i in bin(s & i)[2:]]) % 2 != p:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#ABC128-C
n,m=map(int,input().split())
k=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if ((i>>j)&1):
            l[j]=1
        else:
            l[j]=0
    
    all_s=0
    for x in range(m):
        on=0
        for y in k[x][1:]:
            on+=l[y-1]
            
            
        if on%2==p[x]:#各スイッチがついてるかどうか
            all_s+=1
        else:
            all_s=0
            break
            
    if all_s==m:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    N,M = map(int,input().split())
    K = []
    s = []
    answer = 0
    for _ in range(M):
        ks = list(map(int,input().split()))
        K.append(ks[0])
        s.append(ks[1:])
    p = list(map(int,input().split()))

    for switch in range(0,2**N):

        for j in range(M):
            count = 0
            for k in s[j]:
                if 1 << k-1 & switch:
                    count += 1
            if count%2 == p[j]:
                continue
            else:
                break
        else:
            answer +=1

        
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    switch = [i >> j & 1 for j in range(n)]
    c = 0
    for k, s in enumerate(S):
        count = 0
        for s1 in s:
            if switch[s1-1]:
                count += 1
        if count % 2 == p[k]:
            c += 1
    if m == c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    x = tuple(map(int,input().split()))
    k.append(x[0])
    s.append(x[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    flag = [0] * m
    for j,sj in enumerate(s):
        cnt = 0
        for l in sj:
            if i >> (l-1) & 1:
                cnt += 1
        if cnt % 2 == p[j]:
            flag[j] = 1
    if all(flag):
        ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    #1の時は点灯
    switch = [0] * n
    for j in range(n):
        if((i >> j) & 1):
            switch[j] = 1
    for k in range(m):
        cnt = 0
        for l in range(1,s[k][0] + 1):
            if(switch[s[k][l] - 1] == 1):
                cnt += 1
        if(cnt % 2 != p[k]):
            break
        if(k == m - 1):
            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()))
ans = 0
switch_st = 0
cnt = 0

while switch_st != 2**n:
    switch_on = { i+1 for i in range(n) if switch_st>>i & 1 == 1}
    for i in range(m):
        switch_cnt = len(switch_on & set(k[i][1:]))
        if switch_cnt %2 == p[i]:
            cnt += 1
    else:
        if cnt == m:
            ans += 1
    cnt = 0
    switch_st += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
km = []
for i in range(M):
    tmp = list(map(int, input().split()))
    kk = tmp[0]
    mm = [x-1 for x in tmp[1:]]
    km.append((kk, mm))
P = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    L = list(map(int, list(format(i, '0'+str(N)+'b'))))
    if all([sum([x for i, x in enumerate(L) if i in m[1]]) % 2 == p for m, p in zip(km, P)]):
        ans += 1
print(ans)