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:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,M = inputlist()
switch = [0]*M
k = [0]*M
for i in range(M):
    li = inputlist()
    k[i] = li[0]
    switch[i] = li[1:]
p = inputlist()

ans = 0

for i in range(2**N):
    s = bin(i)
    s = s[2:]
    if len(s) < N:
        for y in range(N-len(s)):
            s = '0'+s
    co = 0
    for j in range(M):
        count = 0
        for t in range(k[j]):
            if s[switch[j][t] - 1] == '1':
                count +=1
        if count % 2 == p[j]:
            co +=1
    if co == M:
        ans +=1

print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << N):
    #矛盾チェック
    flag = True
    for i in range(M):
        sum = 0
        for j in S[i]:
            if bit & (1 << (j-1)):
                sum += 1
        if sum%2 != p[i]:
            flag = False
            break
    if flag:
        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()))

ans = 0
for i in range(2**N):
    Flg = True
    for j in range(M):
        cnt = 0
        for k in range(1, s[j][0]+1):
            if((i>>(s[j][k]-1))&1):
                cnt += 1
        if(cnt%2 != p[j]):
            Flg = False
    if(Flg):
        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()))

ans = 0
for i in range(2**N):
    Flg = True
    for j in range(M):
        cnt = 0
        for m in range(1, len(s[j])):
            for k in range(N):
                if((i>>k)&1 and s[j][m]-1 == k):
                    cnt += 1
        if(cnt%2 != p[j]):
            Flg = False
    if(Flg):
        ans += 1        
print(ans)

Submission status: Accepted

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

def dfs(cur, switch):
    light = [0] * m
    for i in range(n):
        if switch[i]==1:
            for j in range(m):
                if i+1 in t[j]:
                    light[j] = 1-light[j]
    if light == p:
        ret = 1
    else: ret = 0

    if cur == n:
        return ret
    else:
        switch1 = switch.copy()
        switch1[cur] = 1
        return dfs(cur+1, switch) + dfs(cur+1, switch1)

print(dfs(0, [0] * n))

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

res = 0
for i in range(2 ** N):
    ok = True

    for j in range(M):
        cnt = 0
        for k in range(N):
            if i >> k & 1 and (k + 1) in S[j][1:]:
                cnt += 1
        if cnt % 2 != P[j]:
            break

    else:
        res += 1

print(res)

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()))
c = 0

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(1,a+1):
      aa += sw[ks[j][k]-1]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k=[]
s=[]
ans=0

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

for i in range(2**N): #スイッチのon/off 2**N通り
    light=0
    b=bin(i)[2:].zfill(N) #i番目のスイッチのon/offはb[i]の0/1で決まる
    for j in range(M): #豆電球,M通り
        cond=0
        for l in range(k[j]): #豆電球jにつながったスイッチs[j][l]
            cond+=(int(b[s[j][l]-1]))
        if cond%2==p[j]:
            light+=1
    if light==M:
        ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    flag = True
    for m in range(M):
        _sum = 0
        for j in range(N):
            if i >> j & 1:
                _sum += K[m][j]
        if (_sum % 2) != p[m]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s_setlist = []
for i in range(M):
    k, *s = list(map(int, input().split()))
    s_setlist.append(set(s))
plist = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    on = set()
    for j in range(N):
        if ((i >> j) & 1):
            on.add(j+1)
    light_list = [len(on&s_setlist[k])%2==plist[k] for k in range(M)]
    if all(light_list):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#python3

def main():
    n, m = map(int, input().split())
    lamp = []
    for _ in range(m):
       lamp.append([int(i)-1 for i in input().split()][1:]) 
    p = [int(i) for i in input().split()]
    cnt = 0
    for i in range(1<<n):
        partition = [0 for _ in range(n)]
        for j in range(n):
            if i>>j & 1:
                partition[j] = 1
            
        #j番目のlampをみる
        flag = True
        for j in range(m):
            s = 0
            #j番目のlampのk番目のswitchの番号を取り出す
            for k in range(len(lamp[j])):
                v = lamp[j][k]
                if partition[v]:
                    s += 1
            if s%2 != p[j]:
                flag = False
        if flag:
            cnt += 1
    print(cnt)
main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
bulb = []
for i in range(m):
    bulb.append(list(map(int,input().split()))[1:])
p = list(map(int,input().split()))
# print(bulb)
# print(p)
cond = [bin(i)[2:].zfill(n) for i in range(2**n)]
# print(cond)
ans = 0
for i in range(2**n):
    cond_sw = cond[i]
    flag = True
    for j in range(m):
        tar_bulb = bulb[j]
        cnt = 0
        for k in range(len(bulb[j])):
            if cond_sw[tar_bulb[k]-1] == "1":
                cnt += 1
        if cnt % 2 != p[j]:
            flag = False
    if flag:
        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)]
P = list(map(int, input().split()))

ans = 0
for i in range(1<<N):
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    
    flag = True
    # print('cond: ', cond)
    for i in range(M):
        cnt = 0
        for j in switch[i][1:]:
            cnt +=  cond[j-1]
        if cnt%2 != P[i]:
            flag = False
            break
    # print('flag: ', flag)
    # print()
    ans += flag

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
k = []
s = []
for i in range(m):
    tmp = [int(i) for i in input().split()]
    k.append(tmp[0])
    s += [tmp[1:]]
p = [int(i) for i in input().split()]
cnt0 = 0

for b in range(1 << n):

    sw = [0] * n
    for i in range(n):
        if b & (1 << i): sw[i] = 1

    status = True
    for i in range(m):
        cnt1 = 0
        for j in s[i]:
            if sw[j - 1] == 1: cnt1 += 1
        if cnt1 % 2 != p[i]: status = False
    
    if status: cnt0 += 1

print(cnt0)

Submission status: Accepted

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

ans = 0
for i in range(1<<n):
  flag = True
  for j in range(m):
    l = light[j][1:]
    count = 0
    for s in l:
      if i & (1<<(s-1)):
        count += 1
    if count%2 != p[j]:
      flag = False
  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 _ in range(M)]
p = list(map(int, input().split()))

ans = 0
for i in range(1<<N):
    flag = True
    for j in range(M):
        s = ks[j][1:]
        count = 0
        for v in s:
            if i & (1<<(v-1)):
                count += 1
        if count % 2 != p[j]:
            flag = False
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

res = 0
for bit in range(2 ** n): #スイッチの状態
  cc1 = 0
  for i in range(m): #各電球が点くか調べる
    k = S[i][0]
    cc = 0
    for j in range(1, k+1):
      if (bit >> (S[i][j]-1)) & 1:
        cc += 1
    if cc%2 == P[i]:
      cc1 += 1
  if cc1 == m:
    res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
c = 0
from collections import deque
for i in range(2**N):
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    e = 0
    for ii in range(M):
        d = 0
        k = KS[ii][0]
        s = KS[ii][1:]
        for l in s:
            d += bitlist[l-1]#onの数
        d = d%2
        if d != P[ii]:
            e = 1
            break
    if e == 0:
        c += 1
print(c)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
light = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    binstr = list(reversed(format(i, '010b')))
    lightnum = 0
    for j in range(m):
        cnt = 0
        K = light[j][0]
        for k in range(1,K+1):
            s = light[j][k]
            if binstr[s-1] == '1':
                cnt += 1
        if p[j] == cnt%2:
            lightnum += 1
    if lightnum == m:
        ans += 1
print(ans)

Submission status: Accepted

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

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

l_k = []
switches = []
for _ in range(M):
    line = list(map(int, input().split()))
    l_k.append(line[0])
    s = [i - 1 for i in line[1:]]
    switches.append(s)
l_p = list(map(int, input().split()))

# print(N, M)
# print(l_k, switches, l_p)

res = 0
for num in range(2 ** N):
    on_all = True
    for i in range(M):
        n_on = 0
        for s in switches[i]:
            if num & (1 << s):
                n_on += 1
        if n_on % 2 != l_p[i]:
            on_all = False
    if on_all:
        res += 1

print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
ans=0
for bit in range(2**n):
  ok=True
  for j in range(m):
    c=0
    k=s[j][0]
    for l in range(1,k+1):
      if (bit &(1<<(s[j][l]-1))):c+=1
    if c%2!=p[j]:ok=False
  if ok:ans+=1
print(ans)

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(ks[1:])
p = list(map(int, input().split()))

count = 0
for i in range(2**n):
    for j in range(m):
        switch_on = 0
        for k in range(len(s[j])):
            switch_on += (i >> (s[j][k]-1)) & 1
        if switch_on % 2 != p[j]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = []
S = []
for _ in range(M):
    x = input().split()
    k = int(x[0])
    K.append(k)
    S.append([int(x[i]) for i in range(1,k+1)])

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

c = 0
for i in range(2 ** N):
    L = [((i >> j) & 1) for j in range(N)]
    T = "y"
    for j in range(M):
        s = 0
        for k in range(K[j]):
            s += L[S[j][k]-1]
        if s%2 != p[j]:
            T = "n"
            break
    if T == "y":
        c +=1
        
print(c)

Submission status: Accepted

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

count=0
for i in range(1<<n):
    f = True
    for j in range(m):
        pc = 0
        sw = ks[j][1:]
        for s in sw:
            s-=1
            if i&(1<<s):
                pc ^= 1
        if pc != p[j]:
            f = False
    if f:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    answer = 0
    for i in range(2 ** N):
        switch = [0 for _ in range(M)]
        for j in range(N):
            for m in range(M):
                if (i >> j) & 1:
                    if (j + 1) in S[m][1:]:
                        switch[m] += 1
        check = 0
        for m in range(M):
            if switch[m] % 2 == P[m]:
                check += 1

        if check == M:
            answer += 1

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(M):
    input_text = list(map(int, input().split()))
    switches = input_text[1:]
    for switch in switches:
        all_switches[switch - 1].append(i)


# 電球が光る条件(M個)
lightup_terms = list(map(int, input().split()))
# print(all_switches)
count = 0
for i in range(1 << N):
    lightup_counts = [0 for _ in range(M)]
    for j in range(N):
        # 組み合わせを一つずつ確認する
        if i >> j & 1:
            for light in all_switches[j]:
                lightup_counts[light] += 1
    # print(lightup_counts)
    compute_success = True
    for j, term in enumerate(lightup_terms):
        if lightup_counts[j] % 2 != term:
            compute_success = False
            break
    if compute_success:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]
k = []
for i in range(m):
  array = [int(i) for i in input().split()]
  k.append(array)

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

for i in range(2**n):
  r = format(i,'b')
  r = r.zfill(n)[::-1]
  for j in range(m):
    for l in range(1,k[j][0]+1):
      chk += int(r[k[j][l]-1])
    if chk % 2 != p[j]:
      chk = 0
      break
    if j == m-1:
      #print(r,chk)
      ans += 1
    chk = 0
  
print(ans)

Submission status: Accepted

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

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

res = 0
for i in range(1<<n):
    on = [0 for _ in range(n)]
    
    for j in range(n):
        if(i & (1<<j)): on[j] = 1
    
    all_on = True
    for j in range(m):
        
        on_num = 0
        for s in ks[j][1: ]:
            if(on[s-1]): on_num += 1

        if(on_num%2 != p[j]):
            all_on = False
            break

    if(all_on): res += 1

print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ld = [[]]
for i in range(M):
  ld.append(list(map(int,input().split())))
lp = [0]+list(map(int,input().split()))

ans = 0
for i in range(2**N):
  bs = format(i,"0{}b".format(N+1))
  det = 1
  for j in range(1,M+1):
    c = 0
    for k in ld[j][1:ld[j][0]+1]:
      if int(bs[k]) == 1:
        c += 1
    if c%2 != lp[j]:
      det = 0
      break 
  if det == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
group_of_s = []
for _ in range(M):
    s = list(map(int,input().split()))[1:]
    group_of_s.append(s)
p = list(map(int,input().split()))
# print("長さは",len(group_of_s))
def lighton(n,s,p):
    on_num = 0
    for si in s:
        # print("n,si,s,pは",n,si,s,p)
        if n>>(si-1)&1 == 1:
            on_num +=1
        else:
            continue
    if on_num%2 == p:
        # print("true")
        return True
    else:
        # print("false")
        return False
ans = 0
for i in range(2**N):
    dummy = 0
    # print(i)
    for j in range(len(group_of_s)):
        # print(i,j)
        if lighton(i,group_of_s[j],p[j])==True:
            # print(i,k[j],p[j])
            dummy += 1
        else:
            break
    if dummy == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
def light(bit,value,tf):
    count = 0
    bit_v = []
    for i in range(len(bit)):
        if bit[i]:
            bit_v.append(i+1)
    for i in range(len(tf)):
        if tf[i] in bit_v:
            count += 1
    if count%2 == value:
        return True
    else:
        return False
k = [0 for _ in range(m)]
s = [0 for _ in range(m)]
for i in range(m):
    s[i] = map(int,input().split())
for i in range(m):
    s[i] = list(s[i])
    s[i] = s[i][1:]
p = list(map(int,input().split()))
bit = list(map(lambda x:list(x),itertools.product([0,1],repeat=n)))
ans = 0
for i in range(len(bit)):
    c = 0
    for j in range(m):
        if light(bit[i],p[j],s[j]):
            c += 1
    if c == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = []
k = []
for _ in range(M):
    x = list(map(int, input().split()))
    k.append(x.pop(0))
    s.append(x)
p = list(map(int, input().split()))
# print(s, k, p)
ans = 0
for i in range(2**N):
    Switches = [0]*N
    for j in range(N):
        if (i >> j) & 1:
            Switches[j] = 1
    # print(Switches)
    Lamps = [0]*M
    for j in range(M):
        for l in range(k[j]):
            if Switches[s[j][l] - 1] == 1:
                Lamps[j] += 1

    # print(Lamps)
    ok = True
    for j in range(M):
        # if Lamps[j] == 0:
        #     ok = False
        #     break
        if Lamps[j] % 2 != p[j]:
            ok = False
            break

    if ok:
        ans += 1
    
print(ans)

Submission status: Accepted

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

num_patterns = 2 ** n
ans = 0
for pattern in range(num_patterns):
    switches = []
    for j in range(n):
        if ((pattern >> j) & 1):
            switches.append(1)
        else:
            switches.append(0)
    # そのぱたーんで、各電球がつくか判定
    count = 0
    for i, lamp in enumerate(lamp_ls):
        # それぞれの電球につながってるスイッチの状況をリストにまとめる
        s_for_lamp = []
        for s in lamp[1:]:
            if switches[s-1] == 1:
                s_for_lamp.append(1)
            else:
                s_for_lamp.append(0)
        if s_for_lamp.count(1) % 2 == p_ls[i]:
            count += 1
    if count == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k,s=[-1]*m,[-1]*m
for i in range(m):
  k[i],*s[i]=map(int,input().split())
  s[i]=[1 if j in s[i] else 0 for j in range(1,n+1)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  l=list(map(int,format(i,'0%db'%n)))
  c=0
  for j in range(m):
    if sum([min(t) for t in zip(l,s[j])])%2==p[j]:
      c+=1
  if c==m:
    ans+=1
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    s = str(bin(i))
    condition = s[2:].zfill(N)

    # for j in range(M):
    #     switch_on = 0
    #     for k in ks[j][1:]:
    #         if condition[k-1] == "1":
    #             switch_on += 1
    #     if switch_on%2 != p[j]:
    #         break
    # else:
    #     ans += 1



    for j in range(M):
        cnt = 0
        for k in ks[j][1:]:
            if condition[k-1] == "1":
                cnt += 1
        if cnt%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

#%%
cnt = 0
for bits in itertools.product([0, 1], repeat=n):
    # ライトの配列の初期化
    lights = [0] * m

    # 電球ごとのONになってるスイッチの数をカウント
    # スイッチのindexでループを回す
    for i in range(n):
        if bits[i] == 1: #スイッチがONのとき
            sw = i + 1 # スイッチの番号
            for j in range(len(ks)): # 全部のlight-switchの配線を確認
                if sw in ks[j][1:]: # 配線がつながってるとき
                    lights[j] += 1 # そのlightに1を加算

    # カウント終了後条件判別
    # 一つもスイッチがONになってないとライトが付きもしない
    # if 0 not in lights:
        # 2で割ったあまり
    m_lights = [l%2 for l in lights]
    if m_lights == p:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools
from pprint import pprint
n,m = map(int,input().split())
klist = []
slist = []
for i in range(m):
    s = list(map(int,input().split()))
    klist.append(s[0])
    slist.append(s[1:])
plist = list(map(int,input().split()))
kklist = klist[:]

status = [(0, 1) for _ in range(n)]
system_status = list(itertools.product(*status))
ans = 0
for i in range(len(system_status)):#順列列挙の中の順列
    for j in range(n):#注目してる順列の要素
        for k in range(m):#slist
            if system_status[i][j] == 1 and j+1 in slist[k]:
                klist[k] -= 1
    for l in range(m):
        if (kklist[l] - klist[l]) % 2 != plist[l]:
            klist = kklist[:]
            break
    else:
        ans += 1
        klist = kklist[:]
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()))
ans=0
for i in range(2**N):
	b=list(str(bin(i)))
	c=b.pop(0)
	c=b.pop(0)
	b=['0']*(N-len(b))+b
	b=list(map(int,b))
	Light=[]
	for i in range(M):
		light=0
		for j in range(1,N+1):
			if j in a[i][1:]:
				light+=b[j-1]
		if light%2==p[i]:
			Light+=[1]
	if Light==[1]*M:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    switch_pattern = bin(i)[2:].zfill(N)
    for j in range(M):
        switch_on = 0
        for k in ks[j][1:]:
            if switch_pattern[k-1] == "1":
                switch_on += 1
        if switch_on%2 != p[j]:
            break
    else:
        ans += 1
print (ans)

Submission status: Accepted

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

    res = 0
    for i in range(pow(2,n)):
        light = [0]*m
        switch = list(map(int, format(i, '0'+str(n)+'b')))
        for j in range(m):
            for connect in G[j]:
                light[j] += switch[connect - 1]
            light[j] += p[j]
            light[j] %= 2
        if sum(light)==0:
            res += 1
            #print(switch)
    print(res)

my_code()

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
for i in range(2 ** N):
    flag = [False] * M
    for k in range(M):
        cnt = 0
        for j in range(N):
            if ((i >> j) & 1): 
                if j + 1 in ks[k][1:]:
                    cnt += 1
        if cnt % 2 == p[k]:
            flag[k] = True
    if all(flag):
        ans += 1       
print(ans)

Submission status: Accepted

Solution code:
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]
ilm = lambda n: [int(sys.stdin.buffer.readline().split()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    S = [il()[1:] for _ in range(M)]
    P = il()

    ans = 0
    for i in range(1 << N):
        for m in range(M):
            cnt = 0
            for j in range(N):
                if i >> j & 1 and j+1 in S[m]:
                    cnt += 1
            if cnt % 2 != P[m]:
                break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def count_on_switch(switch_array: list, on: set):
    return sum([int(sw in on) for sw in switch_array])

ans = 0
# print("---")
for i in range(2**N):
    on = set()
    for j in range(N):
        if ((i >> j) & 1):
             on.add(j+1)
    temp = 0
    for _ in range(M):
        cou_on = count_on_switch(slist[_], on)
        # print(i, cou_on)
        if cou_on % 2 != plist[_]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    flg = True
    for j in range(m):
        count = 0
        for k in range(1,x[j][0]+1):
            
            if (i>>(x[j][k]-1)&1):
                count += 1
        if count%2 == p[j]:
            continue
        else:
            flg=False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
S = [list(map(int,input().split()))[1:] for i in range(m)]
P = list(map(int,input().split()))
ans = 0
#bit全探索
for bit in range(1<<n):
    on = []
    ok = True #全部の電球が光る
    for i in range(n):
        if (bit & (1<<i)):
            on.append(i+1)
    for i in range(m):
        p = P[i]
        c = 0
        for s in S[i]:
            if s in on: c+=1
        if c%2!=p: ok=False
    if ok:ans+=1
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    u = 1
    e = str(format(i,'010b'))
    for j in range(m):
        if u == 0:
            break
        kar = 0
        for k in range(x[j][0]):
            if e[10-x[j][k+1]] == "1":
                kar += 1
        if kar % 2 != p[j]:
            u = 0
            break
    if u == 1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ks=[list(map(int,input().split())) for _ in range(m)]
    p=list(map(int,input().split()))
    ans=0
    for i in range(2**n):
        for j in range(m):
            cnt,flg=0,1
            for k in ks[j][1:]:
                if i>>(k-1)&1:
                    cnt+=1
            if cnt%2==p[j]:
                continue
            else:
                flg=0
                break
        ans+=flg
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
KS = [lr() for _ in range(M)]
P = lr()
answer = 0
for pattern in itertools.product([0, 1], repeat=N):
    bl = True
    for i in range(M):
        if sum(pattern[x-1] for x in KS[i][1:]) % 2 != P[i]:
            bl = False
            break
    if bl:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 128
# C - Switches
# https://atcoder.jp/contests/abc128/tasks/abc128_c
N, M = map(int, input().split())
S = [tuple(map(int, input().split()[1:])) for _ in range(M)]
*P, = map(int, input().split())

switch2bulb = [[] for _ in [0]*N]

for i, ss in enumerate(S):
    for s in ss:
        switch2bulb[s-1].append(i)

ans = 0
for bit in range(2**N):
    sw = [p ^ 1 for p in P]
    for i in range(N):
        if bit >> i & 1:
            for m in switch2bulb[i]:
                sw[m] ^= 1
    if all(sw):
        ans += 1
print(ans)