Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
ks_list = []
p_list = []
for i in range(M):
    ks_list.append(map(int, raw_input().split()))
p_list.append(map(int, raw_input().split()))

ans_count = 0
for i in range(2**N):
    
    cond = 0
    switch_list = [0]*N
    for j in range(N):
        switch_list[j]=(i>>j)&1

    for m in range(M):
        tmp_count = 0
        for k in range(ks_list[m][0]):
            if switch_list[ks_list[m][1+k]-1] == 1:
                tmp_count = tmp_count + 1

        if p_list[0][m] == (tmp_count % 2):
            cond = 1
        else:
            cond = 0
            break
    if cond == 1:
        ans_count = ans_count + 1
print ans_count

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [x for x in map(int, input().split())]
n, m = map(int, input().split())
#print("sp", n, q, file=sys.stderr)

# 改行区切りの整数の入力
a = []
for x in range(m):
  a.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()


def doit(s):
  ok = True
  for x in range(m):
    res = 0
    for y in range(a[x][0]):
      if s[a[x][y+1]-1] == 1:
        res = res + 1
    #print("res", res, file=sys.stderr)
    if res % 2 != p[x]:
      ok = False
      break
  #print("ok", ok, file=sys.stderr)
  return ok

def createSw(n):
  if n <= 1:
    return [[0,], [1,]]

  ret = []
  for x in createSw(n-1):
    #print("sw0", x, file=sys.stderr)
    ret.append(x + [0])
    ret.append(x + [1])
    #print("ret", ret, file=sys.stderr)
  #print("ret", ret, file=sys.stderr)
  return ret

#print(doit([0] * 4))
try:
  res = 0
  for x in createSw(n):
    if doit(x):
      res = res + 1
  print(res)
except Exception as e:
  print("e", e, file=sys.stderr)

Submission status: Accepted

Solution code:
#coding:utf-8
import itertools
import numpy as np
ls_S = []
N,M = map(int,input().split())
for m in range(M):
    S = list(map(int,input().split()))
    S = [s-1 for s in S]
    ls_S.append(S[1:])
ptns = list(itertools.product(range(0,2), repeat=N))
ptns = np.array(ptns)
#print (ptns)
#print (ls_S)
P = list(map(int,input().split()))
def check(P,ls):
    for i in range(len(P)):
        if P[i] == ls[i]:
            pass
        else:
            return 0
    return 1
sm = 0        
for ptn in ptns:
    ans = []
    for S in ls_S:
        #print ("a",sum(ptn[S]))
        ans.append(sum(ptn[S])%2)
    #print (ans)
    sm += check(P,ans)
print (sm)

Submission status: Accepted

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

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

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

def calc(n,aaa):
    if n == N:
        abc = 0
        for i in range(M):
            ans = 0
            for j in range(1,ks[i][0]+1):
                ans += int(aaa[ks[i][j]-1])
            if p[i] == ans % 2:
                abc += 1

        if abc == M:
            return 1
        else:
            return 0

    ans1 = calc(n+1,aaa + '0')
    ans2 = calc(n+1,aaa + '1')

    return ans1 + ans2

print(calc(0,''))

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int,input().split())
x = []
for _ in range(m):
  k = list(map(int,input().split()))
  x.append(k[1:])
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
  code = "0"*(n-len(bin(i))+3) + bin(i)[2:]
  c = np.array([])
  for j in range(n+1):
    c = np.append(c,int(code[j]))
  for i in range(m):
    if int(sum(c[x[i]]))%2 != p[i]:
      count += 1
      break
print(2**n - count)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M = map(int, input().split())
a = np.zeros((M,N), dtype='int8')
for n in range(M):
    for c in input().split()[1:]:
        a[n, int(c) - 1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for case in itertools.product(range(2), repeat=N):
    np_case = np.array(case)
    b = np.sum(a * np_case, axis=1) % 2
    if all(p == b):
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet%2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m = map(int,input().split())
S = []
for i in range(m):
    A = [int(i)-1 for i in input().split()]  
    S.append(A[1:])
P = list(map(int,input().split()))
ass = ["1","0"]
for i in range(n-1):
    ass2 = []
    for x in ass:
        ass2.append(x+"1")
        ass2.append(x+"0")
    ass = ass2[::]
res = 0
for a in ass:   
    cnt = 0 
    for i in range(m):
        tmp = 0
        for j in S[i]:
            if a[j] == "1":
                tmp += 1
        if tmp%2 == P[i]:
            cnt +=1
    if cnt == m:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
lights = []
for i in range(M):
    lights.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]

ans = 0
switches = 0b1111111111 >> (10 - N)
for _ in range(0, switches + 1):
    flag = True
    for i in range(M):
        s = 0
        for j in range(1, lights[i][0] + 1):
            s += (_ & (0b1 << (lights[i][j] - 1))) >> (lights[i][j] - 1)
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# ABC128C - Switches
from itertools import product

n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
con = list(map(int, input().rstrip().split()))
ans = 0
for i in product(range(2), repeat=n):
    cnt = 0
    for j in range(m):
        ons = 0
        for k in lst[j][1:]:
            if i[k - 1] == 1:
                ons += 1
        if ons % 2 == con[j]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import pprint
import numpy as np

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

    data = list()
    for _ in range(M):
        status = [0 for i in range(N)]
        tmp = list(map(int, input().split()))
        for i in tmp[1:]:
            status[i-1] = 1
        data.append(status)

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

    seq = (0, 1)
    candidates = list(itertools.product(seq, repeat=N))

    result = 0
    for candi in candidates:
        candi = np.array(candi)
        
        i = 0
        for bulb in data:
            bulb = np.array(bulb)
            tmp = list(bulb * candi)
            if sum(tmp)%2 != bulbs_on[i]:
                result -= 1
                break
            i+=1
        result += 1
    
    print(result)
            

if __name__ == "__main__":
    main()

Submission status: Accepted

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

klist = []
sdict = {}
for m in range(M):
    tmp = list(map(int, input().split()))
    klist.append(tmp[0])
    sdict[m] = tmp[1:]
plist = list(map(int, input().split()))

def solve(N, plist, switch_num):
    global M
    num = 0

    if N == 1:
        idx = []
        idx2 = []
        count = 0
        for m in range(M):
            if switch_num in sdict[m]:
                count += 1
                idx.append(plist[m])
            else:
                idx2.append(plist[m])
        if sum(idx) == len(idx) or sum(idx) == 0:
            if sum(idx2) == 0:
                if count == 0:
                    return 2
                else:
                    return 1
            else:
                return 0
        else:
            return 0

    # switch1 == OFF
    new_plist = plist
    num += solve(N-1, new_plist, switch_num+1)
    
    # switch1 == ON
    new_plist = []
    for i in range(M):
        if switch_num in sdict[i]:
            new_plist.append(1 - plist[i])
        else:
            new_plist.append(plist[i])
    num += solve(N-1, new_plist, switch_num+1)

    return num

print(solve(N, plist, 1))

Submission status: Accepted

Solution code:
import itertools
N,M = input().split()
N = int(N)
M = int(M)
line_list = []
for i in range(M):
    line = input().split()
    new_list=[]
    for l in line:
        new_list.append(int(l))
    new_list.pop(0)
    line_list.append(new_list)
old_p_list = input().split()
p_list = []
for p in old_p_list:
    p_list.append(int(p))

A = []
for n in range(N):
    A.append([True,False])
pattern_list = list(itertools.product(*A))
pattern_num = 0
for pattern in pattern_list:
    ok_flug = 1
    for i, line in enumerate(line_list):
            on_num = 0
            for l in line:
                if pattern[l-1]:
                    on_num += 1
            if on_num%2 != p_list[i]:
                ok_flug = 0
    if ok_flug == 1:
        pattern_num += 1
print(pattern_num)

Submission status: Accepted

Solution code:
import copy


args = input().split()
N, M = int(args[0]), int(args[1])
args_list = [list(map(lambda x: int(x), input().split())) for i in range(M)]
p_list = list(map(lambda x: int(x), input().split()))

count = 0
for i in range(2**N):
  continue_state = True
  args_i = copy.deepcopy(args_list)
  bin_str = format(i, "0{}b".format(N))
  bin_list = [int(bin_str[i]) for i in reversed(range(N))]
  bin_list = [i+1 for i, bit in enumerate(bin_list) if bit == 1]
  for j, current_list in enumerate(args_i):
    on_switchs = 0
    del current_list[0]
    for bin in bin_list:
      if bin in current_list:
        on_switchs += 1
    if on_switchs % 2 != p_list[j]:
      continue_state = False
      break
  if continue_state is False:
    continue
  count += 1
print(count)

Submission status: Accepted

Solution code:
from functools import partial
from itertools import product
import numpy as np


def main():
    N, M = map(int, input().split())
    k = []
    s = []
    for _ in range(M):
        input_list = list(map(int, input().split()))
        k.append(input_list[0])
        s.append(input_list[1:])
    ps = list(map(int, input().split()))
    candidates = np.array(list(product([0, 1], repeat=N)))
    for i in range(M):
        index = s[i]
        p = ps[i]
        candidates = list(map(partial(is_match, index=index, p=p), candidates))
        candidates = [c for c in candidates if not isinstance(c, type(None))]
        if candidates == None:
            candidates = []
            break
    print(len(candidates))


def is_match(candidate, index, p):
    if sum(candidate[np.array(index) - 1]) % 2 == p:
        return candidate


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

ans_sum = 0
pre_ = 0
for i1 in [0, 1]:
    for i2 in [0, 1]:
        for i3 in [0, 1]:
            for i4 in [0, 1]:
                for i5 in [0, 1]:
                    for i6 in [0, 1]:
                        for i7 in [0, 1]:
                            for i8 in [0, 1]:
                                for i9 in [0, 1]:
                                    for i10 in [0, 1]:
                                        p_ = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        pre = p_[:N]
                                        if pre == pre_:
                                            break
                                        ans_ = 0
                                        for q in range(M):
                                            ans = 0
                                            for r in range(sk[q][0]):
                                                ans+=pre[sk[q][r+1]-1]
                                            if ans%2 == p[q]:
                                                ans_ +=1
                                        
                                        if ans_ == M:
                                            ans_sum += 1
                                            

                                        pre_ = pre

print(ans_sum)

Submission status: Accepted

Solution code:
import numpy as np
NM= list(map(int,input().split()))
N = NM[0]
M = NM[1]

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

P = list(map(int,input().split()))
Pt = np.zeros((len(P),1))
for i in range(len(P)):
    Pt[i,0]=P[i]

ta = np.zeros((M,N))
for i in range(M):
    for j in range(len(S[i])):
        ta[i,S[i][j]-1]=1

sta = np.zeros((N,1))

count = 0
def func(k):
    global count
    global sta
    global ta
    global Pt
    global N
    for i in range(2):
        sta[k]=i
        if k+1 < N:
            func(k+1)
        if (np.dot(ta,sta)%2==Pt).all() and k==N-1:
            count+=1

func(0)
print(int(count))

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
linkedBulb=[[] for i in range(N)]#各スイッチごとにつながってる電球
for i in range(M):
    S=[int(_) for _ in input().split()]
    for n,s in enumerate(S):
        if n==0:continue
        else:
            linkedBulb[s-1].append(i)
s=[1-int(i) for i in input().split()]
ans=0
for bit in range(2**N):
    start=copy.deepcopy(s)
    for j in range(N):
        if (bit>>j)&1:
            for todo in linkedBulb[j]:
                start[todo]=1-start[todo]
    if all(start):ans+=1
print(ans)

Submission status: Accepted

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

bins = []
for i in range(2**N):
    bins.append(format(i,'b').zfill(N))

cnt = 0
for j in range(2**N):
    b = bins[j]
    accept = 0
    for k in range(M):
        Li = List[k]
        ones = 0
        for l in range(Li[0]):
            if b[Li[l+1]-1]=='1':
                ones+=1
        if ones%2==ps[k]:
                accept+=1
    if accept==M:
        cnt+=1

print(cnt)

Submission status: Accepted

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

all_list = []
for i in range(2**N):
    all_list.append([])
    num_str = bin(i)[2:]
    if len(num_str) < N:
        for j in range(N - len(num_str)):
            all_list[i].append(0)
    for k in range(len(num_str)):
        all_list[i].append(int(bin(i)[2:][k]))


ans_num = 0
a = 0
for ans in all_list:#答えのこうほ
    flag = True

    for i, ks in enumerate(ks_list):# 条件
        middle_ans = 0
        for j in range(1,len(ks)):
            
            middle_ans += ans[ks[j]-1]
        
        if middle_ans % 2 == p_list[i]:
            a += 1
        else:
            flag = False
        
    if flag == True:
        ans_num += 1
print(ans_num)

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()))
a=[bin(j)[2:].zfill(n) for j in range(2**n)]
ans=0
for jj in range(2**n):
  b=0
  for i in range(m):
    num=0
    for ii in range(1,s[i][0]+1):
      num+=int(a[jj][s[i][ii]-1])
    if num%2!=p[i]:
      b+=1
  if b==0:
    ans+=1
print(ans)

Submission status: Accepted

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

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

def dfs(swi):
    global  ans
    #最後まで決めた
 
    if len(swi) == n:
        flag = True
        for i in range(m):
            cnt = 0
            for pos in switch[i]:
                if swi[pos-1] == "1":
                    cnt += 1
            if cnt % 2 != p[i]:
                flag = False
        if flag == True:
            ans += 1
    else:

        dfs(swi+"1")

        dfs(swi+"0")




dfs("")
print(ans)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    ks = []
    bitnums = []
    for i in range(m):
        ks.append(list(map(int, input().split())))
        bitnum = 0
        for j in range(1, ks[i][0]+1):
            bitnum += 1 << (ks[i][j]-1)
        bitnums.append(bitnum)
    p = list(map(int, input().split()))

    np = [1] * (2**n)

    for i in range(len(np)):
        for j in range(m):
            cnt = bin(i & bitnums[j]).count("1")
            if(cnt % 2 != p[j]):
                np[i] = 0
                break
    
    #for i in range(len(np)):
    #    print("{0} {1}".format(np[i], bin(i)))
        
    print(sum(np))

Submission status: Accepted

Solution code:
# coding=utf-8

###
### for atcorder program
###

import sys
import math
import array

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

def main():
    N, M = [int(x) for x in input().split()]
    K = []
    S = []
    
    for i in range(M):
        temp = [int(x) for x in input().split()]
        K.append(temp.pop(0))
        S.append(temp)

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

    ans = 0

    for i in range(2**N):
        tentoucount = 0
        swich = []
        num = bin(i).lstrip('0b').zfill(N)
        for j in num:
            swich.append(int(j))

        for j in range(M):
            onswich = 0
            for k in S[j]:
                onswich += swich[k-1]
            if onswich%2 == P[j]:
                tentoucount += 1

        if tentoucount == M:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import itertools

def main():
    n,m = [int(x) for x in stdin.readline().rstrip().split()]
    ss = []
    for x in range(m):
        ks = tuple(map(int, stdin.readline().rstrip().split()))
        ss.append(ks[1:])
    ps = [int(x) for x in stdin.readline().rstrip().split()]

    ans = 0
    for cond in itertools.product((0,1), repeat=n):
        ok = 1
        for s,p in zip(ss,ps):
            total = 0
            for c in s:
                total += cond[c-1]
            if total % 2 != p:
                ok = 0
                break
        ans += ok

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

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int,input().split())
li = []
for i in range(m):
    li_buf = list(map(int,input().split()))
    li.append(li_buf)
# print(li)
p = list(map(int,input().split()))
# print(p)

li_com = []
li_flag = [[True, False] for i in range(10)]
for a, b, c, d, e, f, g, h, i, j in product(li_flag[0], li_flag[1], li_flag[2], li_flag[3], li_flag[4], li_flag[5], li_flag[6], li_flag[7], li_flag[8], li_flag[9]):
    li_com.append([a, b, c, d, e, f, g, h, i, j])

for i in range(m):
    buf = []
    for j in range(len(li[i])):
        if j == 0:
            continue
        buf.append(li[i][j])
    li_com_2 = []
    for k in range(len(li_com)):
        buf_2 = []
        for l in range(len(buf)):
            buf_2.append(li_com[k][buf[l]-1])
        if buf_2.count(True) % 2 == p[i]:
            li_com_2.append(li_com[k])
    li_com = li_com_2
print(int(len(li_com)/ 2 ** (10 - n)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = 0
ss = []
for i in range(m):
    k, *s = map(int, input().split())
    ss.append(s)
ps = list(map(int, input().split()))
for i in range(2**n):
    status = format(i, 'b').zfill(n)
    areAllLit = True
    for j in range(m):
        amount = 0
        for k in ss[j]:
            if status[k-1] == '1':
                amount += 1
        if amount % 2 != ps[j]:
            areAllLit = False
    if areAllLit:
        ans += 1
print(ans)

Submission status: Accepted

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

num=2**n
count=0
for i in range(num):
    lump=1
    x=[]
    for j in range(n):
        x.append((i*2//(2**(j+1)))% 2)
    for k in range(m):
        sum=0
        for k1 in range(len(list1[k][1:])):
            if x[list1[k][k1+1]-1]==1:
                sum=sum+1
        if sum % 2!=p[k]:
            lump=0
    if lump==1:
        count=count+1
print(count)

Submission status: Accepted

Solution code:
import math


def main():
    N, M = map(int, input().split())
    state = [list(map(int, input().split())) for i in range(M)]
    p = [int(s) for s in input().split()]

    s = [0] * N
    ans = 0
    # 全事象
    for j in range(2 ** N):
        # スイッチの状態作成
        temp = j
        for i in range(N):
            s[i] = temp % 2
            temp = temp >> 1

        lamp = [0] * M
        for i in range(M):
            temp = 0
            for k in state[i][1:]:
                temp += s[k - 1]
            if temp % 2 == p[i]:
                lamp[i] = 1

        if all(lamp):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for t in product([0, 1], repeat=N):
    sw = {i+1: t[i] for i in range(N)}
    flg = 1
    # 電球確認
    for ind in range(M):
        num = 0
        # スイッチON個数確認
        for j in s[ind]:
            if sw[j] == 1:
                num += sw[j]
        # 電球OFF時はnot answer
        if num % 2 != p[ind]:
            flg = 0
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = map(int, input().split())
    # k1 s11, s12, s13, ..., s1k1
    KS_list = [list(map(int, input().split())) for i in range(M)]
    P_list = list(map(int, input().split()))

    answer = 0
    for i in range(2**N):
        pattern = str(bin(i)).replace('0b','').zfill(N)
        is_all_light_on = True
        for j in range(M):
            KS_j = KS_list[j]
                # list(map(int, KS_list[j].split()))
            K_j = KS_j[0]
            S_j = KS_j[1::]

            on_switch_cnt = 0
            for s in S_j:
                if pattern[s-1] == '1':
                    on_switch_cnt += 1

            if on_switch_cnt%2 != P_list[j]:
                is_all_light_on = False

        if is_all_light_on == True:
            answer += 1
    print(answer)

Submission status: Accepted

Solution code:
import itertools as it
N,M = map(int,input().split())
slk = []
for _ in range(M):
    slk.append(list(map(int,input().split())))
p = list(map(int,input().split()))
#print(N,M)
#print(slk)
#print(p)

s = [i+1 for i in range(N)]
cb = 0
for i in range(N+1):
    cmbi = list(it.combinations(s, i))
    #print('i,cmbi:',i,cmbi)
    for ccmb in cmbi:
        for j,slki in enumerate(slk):
            g = 0
            #print('slki',slki)
            for k in range(slki[0]):
                if slki[k+1] in ccmb:
                    g += 1
            #print('g,p:',g,p[j])
            if g%2 == p[j]:
                pass
            else:
                #print('error')
                break
        else:
            cb += 1
            #print('add succ;',cb)
print(cb)

Submission status: Accepted

Solution code:
import itertools

def is_lit(i, bit):
    l = [bit[j-1] for j in sockets[i]]
    return p[i] == l.count(True) % 2

count = 0
N, M = map(int, input().split())
bit_list = list(itertools.product([True, False], repeat = N))

sockets = []
for i in range(M):
    args = input().split(' ')
    k = int(args[0])
    sockets.append([int(args[i+1]) for i in range(k)])

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

for bit in bit_list:
    o = [is_lit(i, bit) for i in range(M)]
    if o.count(True) == len(o):
        count += 1

print(count)

Submission status: Accepted

Solution code:
from copy import deepcopy
N,M = map(int,input().split())
s_list = []
for _ in range(M):
    s_list.append(tuple(map(int,input().split()[1:])))
plist = tuple(map(int,input().split()))

counter = 0
TF = [0]*N
TFlist = []
def make_bbb(long,number):
    b_n = bin(number)[2:]
    bbb = "0"*(long-len(b_n))+b_n
    return bbb
for _ in range(2**N):
    number = list(map(int,list(make_bbb(N,_))))
    TFlist.append(number)


for TF in TFlist:
    flg = False
    ok = 0
    for num,s in enumerate(s_list):
        sum_on = 0
        #各スイッチ
        for ele in s:
            sum_on += TF[ele-1]
        if sum_on%2 != plist[num]:
            flg = False
            break
        else:
            ok += 1
    if ok == M:
        counter += 1


print(counter)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = []
for i in range(m):
        A.append(input().split()[1:])
P = [int(i) for i in input().split()]
ans = 0
for i in range(2**n):
        count = [0] * m
        a = len(bin(i))-2
        for j in bin(i)[2:]:
                if int(j) == 1:
                        for k in range(m):
                                if str(a) in A[k]:
                                        count[k]+=1
                a-=1
        count = [i%2 for i in count]
        if count == P:
                ans += 1
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2**n):
  s = format(i,"b").zfill(n)
  s = [int(x) for x in list(str(s))]
  for j in range(m):
    tmp = 0
    for k in range(li[j][0]):
      tmp += s[li[j][k+1]-1]
    if tmp % 2 != lip[j]:
      break
  else:
    cnt += 1
    continue
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(lambda x: int(x), input().split(' '))
k = []

for i in range(m):
    k.append(list(input().split(' ')[1:]))

p = list(map(lambda x: int(x), input().split(' ')))


on = list(product([False, True], repeat=n))
count = 0

for _on in on:
    for i, _k in enumerate(k):
        if not (([_on[int(__k) - 1] for __k in _k]).count(True) % 2) == p[i]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

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

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

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



foo = [0] * N
hoge = []
def rec(n):
    if (n < 0):
        hoge.append(foo.copy())
        return
    foo[n] = 1
    rec(n-1)
    foo[n] = 0
    rec(n-1)

rec(N-1)

res = 0
for i in hoge:
    flag = True
    for j in range(M):
        tmp = 0
        for k in range(S[j][0]):
            if (i[S[j][k+1]-1]):
                tmp += 1

        if tmp % 2 != P[j]:
            flag = False
            break
    if flag:
        res += 1
    

print(res)