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

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def create_bin_string(data, num):
    c_bin = "{:b}".format(data)
    switches = c_bin
    for _ in range(0, num-len(c_bin)):
        switches = "0" + switches
    return switches


def solve(N, M, data, Ps):
    lamp_sw_comb = list(map(lambda x: string_to_int(x), data))
    lamp_sw_p = string_to_int(Ps)

    count = 0
    for c in range(0, 2**N):
        switches = create_bin_string(c, N)

        are_all_light = True
        for i, lamp_sw in enumerate(lamp_sw_comb):
            on_num = 0
            for j, sw in enumerate(lamp_sw):
                if j == 0:
                    continue
                if switches[sw-1] == "1":
                    on_num += 1
            if on_num % 2 != lamp_sw_p[i]:
                are_all_light = False
                break

        if are_all_light:
            count += 1
    return count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    data = inputs(M)
    Ps = input()
    ret = solve(N, M, data, Ps)
    print(ret)

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
N, M = map(int, input().split())
ss = [None] * M
for i in range(M):
    in_ = list(map(int, input().split()))
    ss[i] = [s-1 for s in in_[1:]]
ps = list(map(int, input().split()))

ans = 0
switch = [0] * N
for x in range(2**N):
    incl = 1
    bin_x = format(x, '0{}b'.format(N))
    switch = np.array([int(bin_x[i]) for i in range(N)])
    for i in range(M):
        if switch[ss[i]].sum() % 2 != ps[i]:
            incl = 0
            break
    ans += incl
        
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

# bitリスト
def getBitsL(n, L):
    bits = [0] * L
    for i in range(L):
        bits[i] = (n & 1) == 1
        n >>= 1
    return bits

def main():
    N, M = i2nn()
    KS = ii2nnn(M)
    P = i2nn()
    n = 0
    for i in range(2**N):
        bits = getBitsL(i, N)
        b = True
        for j, ks in enumerate(KS):
            t = 0
            for k in ks[1:]:
                if bits[k-1]:
                    t += 1
            if t % 2 != P[j]:
                b = False
        if b:
            n += 1
    print(n)

main()

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ss = []
for i in range(M):
  ws = [int(w) for w in input().split()]
  ws.pop(0)
  s = 0
  for w in ws:
    s |= 1 << (w-1)
  ss.append(s)
#print(ss)
ps = [int(w) for w in input().split()]

def countbit(o):
  c = 0
  for n in range(N):
    if o & (1 << n) != 0:
      c += 1
  return c
r = 0
for i in range(1 << N):
  ok = True
  for m in range(M):
    s, p = ss[m], ps[m]
    o = i & s
    c = countbit(o)
    #print(o, c)
    if c % 2 != p:
      ok = False
      break
  if ok:
    r += 1
print(r)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
p=list(map(int,input().split()))
i_b=[]
for i in range(2**n):
  i_b.append(str(bin(i))[2:].zfill(n))
ans=0
for i in i_b:
  i_a=[]
  for j in range(m):
    j_s=0
    for k in range(1,s[j][0]+1):
      j_s+=int(i[s[j][k]-1])
    i_a.append(j_s%2)
  if i_a==p:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# ABC128 C-Switches

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

k = []
s = []
for _ 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 bits in range(2**n):
    flag = True
    for i in range(m):
        on_sum = 0
        for switch in s[i]:
            on_sum += ((bits >> (switch - 1)) & 1)
        flag = flag and ((on_sum % 2) == p[i])
    if flag:
        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()))

ans = 0
for i in range(2 ** n):
    for mi in range(m):
        on_count = 0
        for ni in range(n):
            if (i & (1 << ni)) and (ni + 1 in s[mi]):
                on_count += 1
        if on_count % 2 != p[mi]:
            break
    else:
        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()))

def check(ar):
    cnt = 0
    for j in range(M):
        count = 0
        for k in ks[j][1::]:
            if ar[k-1] == 1:
                count += 1
        if count%2 == p[j]:
            cnt += 1
    return (cnt == M)


def dfs(n, ar):
    if n == 0:
        if check(ar):
            return 1
        else:
            return 0
    else:
        return dfs(n-1, ar+[0]) + dfs(n-1, ar+[1])
arr = []
ans = dfs(N, arr)
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
for i in range(2**N):
    cnt = 0
    for j in range(M):
        count = 0
        for k in ks[j][1::]:
            if (i >> k-1)&1 == 1:
                count += 1
        if count%2 == p[j]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Accepted

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

count = 0
for i in range(2**n):
    on = 0
    for j in range(m):
        cnt = 0
        for s in ks_list[j][1:]:
            if (i >> s-1)&1 == 1:
                cnt += 1
        if cnt%2 == p_list[j]:
            on += 1
    if on == m:
        count += 1
print(count)

Submission status: Accepted

Solution code:
#2bit生成　ON=1 OFF=2
import itertools
L = [0,1]
count = 0

N,M = map(int,input().split())
k = []
s = []

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

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

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

for i in bit_list:
    
    for j in range(M):
        #電球Mのチェック
        counter = 0
        tmp = list(s[j])
        
        for l in tmp:
            if i[l-1] == 1:
                counter += 1
        
        if counter % 2 != p[j]:
            break
        
        if j == M-1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Light = []
for _ in range(M):
    Tmp = list(map(int, input().split()))
    Tmp.pop(0)
    Light.append(set(Tmp))
P = list(map(int, input().split()))

import itertools
bit = list(itertools.product(['On', 'Off'], repeat=N))
ans = [0 for _ in range(2**N)]

for idx in range(M):
    light = Light[idx]
    p = P[idx]
    for j, switchs in enumerate(bit):
        cnt = 0
        for l in light:
            if switchs[l-1] == 'On':
                cnt += 1
        if cnt % 2 == p:
            ans[j] += 1
print(ans.count(M))

Submission status: Accepted

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

list_k = list()
list_p = list()

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

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

answer = 0

for i in range(2 ** n):
    # print(format(i, 'b').zfill(n))

    switch = format(i, 'b').zfill(n)[::-1]

    for idx, p in enumerate(list_p):
        check_k = list_k[idx][1:]

        target_switch = [switch[k - 1] for k in check_k]

        if target_switch.count('1') % 2 != p:
            break
    else:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
from itertools import product
N,M = list(map(int, input().split()))

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

for i in range(M):
  L = list(map(int, input().split()))
  for a in L[1:]:
    A[i][a-1] = 1
    
P = list(map(int, input().split())) 

ans = 0
for X in list(product([0,1], repeat=N)):
  flg = True
  for i in range(M):
    work = 0
    for j in range(N):
      work += A[i][j] * X[j]
      
    if work % 2 == P[i]:
      continue
    else:
      flg = False
      break
  if flg:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int, input().split())
s = []
for _ in range(m):
    _, *t = map(int, input().split())
    s.append(t)
p = [int(i) for i in input().split()]

cnt = 0
for fl in product([0, 1], repeat=n):
    for i in range(m):
        if sum(fl[tmp - 1] for tmp in s[i]) % 2 != p[i]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
swithCount, lightCount = map(int, input().split())
swithList = [0] * swithCount

for lightIndex in range(lightCount):
    connectedSwitchList = list(map(int, input().split()))
    for si in connectedSwitchList[1:]:
        switchIndex =  si - 1
        swithList[switchIndex] = swithList[switchIndex] | 1 << lightIndex

expectedLightStatusList = list(map(int, input().split()))
expectedLightStatus = 0

for i, eachStatus in enumerate(expectedLightStatusList):
    expectedLightStatus = expectedLightStatus | eachStatus << i

resultCount = 0
for eachSwitchSet in range(1 << swithCount):
    actuallyLightStatus = 0
    for switchIndex in range(swithCount):
        if eachSwitchSet >> switchIndex & 1:
            actuallyLightStatus = actuallyLightStatus ^ swithList[switchIndex]

    if expectedLightStatus == actuallyLightStatus:
        resultCount += 1

print(resultCount)

Submission status: Accepted

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

cnt = 0
for i in range(2**n):
    bi = format(i, "010b")[::-1]
    flag = True
    for j in range(len(sl)):
        c = 0
        for idx in sl[j]:
            c += int(bi[int(idx)-1])
        if c % 2 != p[j]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if ((i >> j) & 1 ):
            switch[j] += 1
    on = 0
    for k in range(M):
        count = 0
        for l in range(1,s[k][0]+1):
            if switch[s[k][l]-1] == 1:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == M:
        ans += 1
    
print(ans)

Submission status: Accepted

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

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


n_combi = 0
for combi in range(1 << N):
    Flag = True
    for i in range(M):
        k = ks_lists[i][0]
        s_list = ks_lists[i][1:]
        p = p_list[i]

        tmp_sum = 0
        for s in s_list:
            tmp_sum += (combi >> (s-1)) & 1
        if tmp_sum % 2 != p:
            Flag = False
            break
    if Flag:
        n_combi += 1

print(n_combi)

Submission status: Accepted

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

conditions = list(map(int,input().split(" ")))

p_num = 2**n
count = 0
for i in range(p_num):
  on_switch = []
  flag = True
  for digit in range(n):
    if (i%2 == 0):
      on_switch.append(digit+1)
    i = i//2
  for j in range(m):
    buf = [x for x in on_switch if x in lights[j]]
    if len(buf) % 2 != conditions[j]:
      flag = False
  if flag:
    count += 1

print(count)

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

ans = 0

def tekito(swit):
    for i in range(m):
        judge_kun = 0
        for s in ks[i][1:]:
            judge_kun += swit[s-1]
        if judge_kun % 2 == (1-p[i]):
            return False
    return True

import itertools
for swit in itertools.product([0, 1], repeat=n):
    if tekito(swit):
        ans+=1


print(ans)

Submission status: Accepted

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

count = 0

for i in range(2 ** n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n)
    for j in ks:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k) - 1])
        if swith_sum % 2 == p[ks.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from copy import deepcopy
n, m = map(int, raw_input().split())
S = []
for _ in range(m):
    line = map(int, raw_input().split())
    S.append(line[1:])
P = map(int, raw_input().split())
perms = [[0] * n]
for i in range(n):
    for j in range(len(perms)):
        p2 = deepcopy(perms[j])
        p2[i] = 1
        perms.append(p2)
ways = 0
for perm in perms:
    satisfy = True
    for k in range(m):
        count = 0
        for s in S[k]:
            if perm[s-1] == 1:
                count += 1
        if count % 2 != P[k]:
            satisfy = False
            break
    if satisfy:
        ways += 1
print ways

Submission status: Accepted

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

count= 0

for i in range(2**n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n) 
    for j in info_list:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k)-1])
        if swith_sum%2 == p_list[info_list.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:        
        count += 1

print(count)

Submission status: Accepted

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

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

p = list(map(int,input().split()))
#greedy O(2^N)(MN) : (all set of switch N) = 2^10 * M 10 10^4 OK
ans = 0
for i in range(2**N): # all set of N  2**N == 1 << N (shif operator N right shift)
  for j in range(M): # i_th lump consider
    cnt = 0 
    for k in ls[j]:
      if i&(1<<(k-1)): # if switch k is ON, then return non-zero(True)
        cnt += 1
    if cnt%2 != p[j]:
      break
  else:
    ans +=1
print(ans)

Submission status: Accepted

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

A=[]
total=0
count=0
flag=0
for j in range(M+1):
    A.append(list(map(int, input().split())))

for i in range(2**N):
    switch=format(i,'b')
    switch=switch[::-1]+'0000000000'
    

    for a in range(M):
        for b in range(1,len(A[a])):
            
            count += int(switch[int(A[a][b])-1])
            

        if count%2!=A[M][a]:
            flag=1
        count = 0
    if flag==0:
        total +=1
    flag=0
    count=0
print(total)

Submission status: Accepted

Solution code:
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

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

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            break
    else:
        count += 1
    state = [0 for i in range(M)]
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
D = [0]*M
for i in range(M):
    temp = list(map(int, input().split()))
    for j in temp[1:]:
        D[i] +=  2**(j-1)
p = list(map(int, input().split()))
ans = 0
for s in range(2**N):
    temp = True
    for i,d in enumerate(D):
        temp &= bin(s&d).count('1')%2==p[i]
    if temp:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# n=int(sys.stdin.readline())
# a,b=map(int, sys.stdin.readline().split())
# c=list(map(int, sys.stdin.readline().split()))
# s=[list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import math
import sys

#sys.stdin = open("input.txt")
N, M=map(int, sys.stdin.readline().split())

# 各スイッチがどの電球につながっているかの情報をビットで保持する配列
# 1番目のスイッチが2番目と3番目の電球につながっていた場合以下のようになる
# (1 << 1) | (1 << 2) = (110)b   ※ zero index
bulb_list = [0 for _ in range(N)]

for bulb_idx in range(M):
    switches = list(map(int, sys.stdin.readline().split()))
    bulb_bit = 1 << bulb_idx # つながっている電球を二進数で表す

    # switchesの2番目以降の要素には、スイッチの番号が入っている
    for sw in switches[1::]:
        sw_idx = (sw - 1) # スイッチの番号をzero indexに変換する
        bulb_list[sw_idx] = bulb_list[sw_idx] | bulb_bit

bulb_conds = list(map(int, sys.stdin.readline().split()))

bulb_cond = 0
for i, bc in enumerate(bulb_conds):
    bulb_cond |= bc << i

light_num = 0
# N = 3 の時
# 000, 001, 010, 011, 100, 101, 110, 111 の8パターンで、
# スイッチを押す全てのパターンを表現することが出来る
for bit_ptn in range(1 << N):
    t = 0 # tはbit_ptnが表すスイッチの組み合わせを全て押したときの電球の状態を表す(最初は全部消えている)
    for i in range(N):
        if bit_ptn >> i & 1:
            t = t ^ bulb_list[i]
    if t == bulb_cond:
        light_num += 1

print(light_num)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
connect = [[0,0,0]]
on_off = [0]*(N+1)
result = 0
for _ in range(M):
    k = list(map(int, input().split()))
    connect.append(k[1:])
p = list(map(int, input().split()))

for cnt in range(0,2**N):
    bin_str = list(format(cnt, 'b'))
    i = len(on_off)-len(bin_str)
    for num in bin_str:
        on_off[i] = int(num)
        i += 1
    for i in range(1,M+1):
        total = 0
        for j in connect[i]:
            total += on_off[j]
        if total % 2 != p[i-1]:
            break
        elif i == M:
            result += 1
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    switches = defaultdict(list)
    for i in range(M):
        ks = list(map(int, input().split()))
        for s in ks[1:]:
            switches[s].append(i)
    p_list = list(map(int, input().split()))

    cnt = 0
    for i in range(2 ** N):
        on_nums = defaultdict(int)
        bits = bin(i)[2::][::-1]
        for k, b in enumerate(bits):
            if b == '1':
                for s in switches[k+1]:
                    on_nums[s] += 1

        if all([on_nums[s] % 2 == p_list[s] for s in range(M)]):
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        a = list(map(int, input().split()))
        S.append([b-1 for b in a[1:]])
    P = list(map(int, input().split()))

    # set mask
    mask = [0 for _ in range(M)]
    for i in range(M):
        m = 0
        for s in S[i]:
            m += 2 ** s
        mask[i] = m
    
    ans = 0
    for k in range(2 ** N):
        res = True
        for i in range(M):
            if bin(k & mask[i]).count('1') % 2 != P[i]:
                res = False
                break
        if res:
            ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s_li = []
k = []
for i in range(m):
    ks = list(map(int, input().split()))
    k.append(ks[0])
    ks.pop(0)
    s_li.append(ks)
p = list(map(int, input().split()))

bit_li = []
for i in range(2**n):
    bit = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            bit[j] = 1
    bit_li.append(bit)

count = 0
for i in range(2 ** n):
    flag = 0
    for j in range(m):
        elem_sum = 0
        for l in range(k[j]):
            elem_sum += bit_li[i][s_li[j][l] - 1]
        if elem_sum % 2 == p[j]:
            flag += 1
    if flag == m:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

        v = [0] * N
        for s in S[1:]:
            v[s - 1] = 1
        state.append(v)
    P = list(map(int, input().split()))

    ans = 0
    for pattern in product([0, 1], repeat=N):
        all_on = True
        for i in range(M):
            num_on = 0
            for j in range(N):
                if state[i][j] == 1 and pattern[j] == 1:
                    num_on += 1

            if num_on % 2 != P[i]:
                all_on = False
                break

        ans += all_on

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

S = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
K = [S[i][0] for i in range(M)]
#print("S",S)
#print("P",P)
#print("K",K)

ans = 0

for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if (i >> j)  & 1:
            switch[j] = 1
    #print(switch)
    flag = 0
    for j in range(M):
        tmp = 0
        for k in range(1,K[j]+1):
            if switch[S[j][k] - 1] == 1:
                tmp += 1#switch on の数
        #print("tmp",tmp)
        if tmp % 2 != P[j]:
            flag = 1
            break
    if not flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = list([int(i) for i in input().split()] for i in range(M))
p = list(map(int, input().split()))
count = 0

for i in range(2**N):
  onoff = [0]*N
  flag = 0
  for j in range(N):
    if (i >> j) & 1:
      onoff[j] = 1
  for k in range(M):
    tmp = 0
    for l in range(S[k][0]):
      if onoff[S[k][l+1]-1] == 1:
        tmp += 1
    if tmp%2 == p[k]:
      continue
    else:
      flag = 1
      break
    
  if flag == 0:
    count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n,m=list(map(int, input().split()))
switches=[]
for i in range(m):
    l1=list(map(int, input().split()))[1:]
    s=0
    for i in l1:
        s+=1<<(i-1)
    switches.append(s)
remainders=list(map(int, input().split()))
answer=0
for i in range(1<<n):
    is_all_lighted=True
    for j,s in enumerate(switches):
        if bin(s&i).count("1")%2 != remainders[j]:
            is_all_lighted = False
    if is_all_lighted == True:
        answer+=1
print(answer)

Submission status: Accepted

Solution code:
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 i in range(2**n):
    ls = []
    for j in range(n):
        if (i>>j)&1:
            ls.append(j+1)
    
    flg = 1
    for k in range(m):
        if len(set(s[k])&set(ls))%2==p[k]:
            pass
        else:
            flg = 0
    if flg ==1:
        ans +=1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N, M = map(int,stdin.readline().rstrip().split())
switchList=[]
for i in range (M):
  switchList.append(list(map(int, stdin.readline().rstrip().split())))
pList = list(map(int, stdin.readline().rstrip().split()))

methodCounter=0
for i in range(2**N):
  lightOnCounter=0
  for j in range (M):
    k = switchList[j][0]
    onCounter=0
    for l in range (1,k+1,1):
      switch=switchList[j][l]
      bit = 1 << switch-1
      if (i & bit) != 0:
        onCounter+=1
    if onCounter %2 == pList[j]:
      lightOnCounter+=1
  if lightOnCounter == M:
    methodCounter+=1
print(methodCounter)

Submission status: Accepted

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

ans = 0
for i in range(0,2**n):
	bi_str = format(i, '0'+str(n)+'b')
	#print(bi_str)
	flag = True
	for j in range(len(s)):
		#print(s[j])
		switch = 0
		for x in s[j]:
			if bi_str[x-1] == str(1):
				switch += 1
		#print(switch)
		#print(p[j])

		if switch%2 != p[j]:
			flag = False
	if flag:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()


N,M = na()
light = []
for i in range(M):
    t = na()
    s = 0
    for i in t[1:]:
        s += 1 << (i-1)
    light.append(s)

ppp = na()
sum_s = 0
for i in range(1<<N):
    t=0
    for s,p in zip(light,ppp):
        if p == bin(i&s).count("1")%2:
            t+=1
    if t == M:
        sum_s+=1
print(sum_s)

Submission status: Accepted

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

ans=0
for i in range(1<<N):
    flg=True

    for c,s in enumerate(sw):
        s_on=0
        for bit in s:
            if ((i >> (bit-1)) & 1) == 1:
                s_on+=1
        if s_on%2!=p[c]:
            flg=False

    if flg:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

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

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            break
    else:
        count += 1
    state = [0 for i in range(M)]
print(count)

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    n, m, *ksp = map(int, string.split())
    p = ksp[-m:]
    ans = 0
    for t in product([True, False], repeat=n):
        index = 0
        for i, _p in enumerate(p):
            k = ksp[index]
            use = ksp[index + 1:index + 1 + k]
            index += k + 1
            if sum([t[j - 1] for j in use]) % 2 != _p:
                break
        else:
            ans += 1
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m + 1)])))

Submission status: Accepted

Solution code:
import math

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

cnt = 0
for i in range(int(math.pow(2,n))):
    isall_lighted = True
    bin = i
    onoff = [0]*n
    for i in range(n):
        digit = int(math.pow(2, i+1))
        if bin % digit != 0:
            onoff[i] = 1
            bin = bin - digit//2

    for i, light in enumerate(s):
        sw_cnt = 0
        for sw in light:
            sw_cnt += onoff[sw-1]
        if sw_cnt % 2 != p[i]:
            isall_lighted = False
    if isall_lighted:
        cnt += 1

print(cnt)