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
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n, m = map(int, input().split())
    light_bulbs = {i: [] for i in range(m)}
    for i0 in range(m):
        data = tuple(map(int, input().split()))
        light_bulbs[i0]= data[1:]
    p = tuple(map(int, input().split()))

    pat = tuple(product((0, 1), repeat=n))
    res = 0
    for pate in pat:
        light_on = 0
        for i, bulb in enumerate(light_bulbs.values()):
            turned_switch = 0
            for bulb_switch in bulb:
                turned_switch += pate[bulb_switch - 1]
            if turned_switch % 2 == p[i]:
                light_on += 1
        if light_on == m:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def read(): return sys.stdin.readline() # 標準入力
def fbit(i, j=-1): return format(i, 'b').zfill(j) # bit 表示
def popcount(x): # ビットカウント
    x=x-((x>>1)&0x5555555555555555)
    x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)
    x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f;x=x+(x>>8);x=x+(x>>16);x=x+(x>>32)
    return x&0x0000007f


def solv(N:int, M: int, k:list, s: list, p: list):
    ans = 0
    for bits in range(1<<N):
        flag = True
        for i in range(M):
            mask = 0
            for j in s[i]:
                mask = mask|1<<(j-1)
            if not popcount(bits&mask)%2==p[i]: flag = False
        if flag: ans += 1
    print(ans)

def main():
    [N, M] = list(map(int, read().rsplit()))
    k = []; s = []
    for i in range(M):
        _tmp = list(map(int, read().rsplit()))
        k.append(_tmp.pop(0))
        s.append(_tmp)

    p = list(map(int, read().rsplit()))
    solv(N, M, k, s, p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def read(): return sys.stdin.readline() # 標準入力
def fbit(i, j=-1): return format(i, 'b').zfill(j) # bit 表示
def popcount(x): # ビットカウント
    x=x-((x>>1)&0x5555555555555555)
    x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)
    x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f;x=x+(x>>8);x=x+(x>>16);x=x+(x>>32)
    return x&0x0000007f


def solv(N:int, M: int, k:list, s: list, p: list):
    ans = 0
    for bits in range(1<<N): # スイッチの状態を全て列挙(bit全探査)
        # ビットの数をカウント
        # count = popcount(bits)
        flag = True
        for i in range(M): # 点灯条件 M[i]でpopcount%2=p[i]
            # マスクビット用のmaskを作成
            mask = 0
            # 各電球の利用可能スイッチをマスクで取得 => 1,2 なら　0b11とか
            for j in s[i]:
                mask = mask|1<<(j-1)
            # print(fbit(mask))
            # ビットカウント => 条件分岐
            if not popcount(bits&mask)%2==p[i]: flag = False
        if flag: ans += 1
    print(ans)

def main():
    [N, M] = list(map(int, read().rsplit()))
    k = []; s = []
    for i in range(M):
        _tmp = list(map(int, read().rsplit()))
        k.append(_tmp.pop(0))
        s.append(_tmp)

    p = list(map(int, read().rsplit()))
    solv(N, M, k, s, p)


if __name__ == '__main__':
    main()



2&3

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
 
ans = 0
for i in range(2**n):
    light = 0
    for ki, j in enumerate(k):
        switch = 0
        for s in j[1:]:
            if i & (1 << s-1):
                switch += 1
        if switch % 2 == p[ki]:
            light += 1
    if light == m:
        ans += 1
print(ans)

Submission status: Accepted

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

s_lst = [[False] * N for _ in range(M)]
for i in range(M):
    ks = list(map(int, input().split()))
    for j, value in enumerate(ks):
        if j != 0:
            s_lst[i][value-1] = True
p = list(map(int, input().split()))
# print(s_lst)

ans = 0
for bit in range(2**N):
    cnt = [0] * M
    for i in range(N):
        if (bit>>i) & 1 == 1:
            for j in range(M):
                if s_lst[j][i]:
                    cnt[j] += 1
    flug = True
    for i in range(M):
        if cnt[i] % 2 != p[i]:
            flug = False
    if flug:
        ans += 1
print(ans)

Submission status: Accepted

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

smi = [ None ] * m

for i in range(m):
    k, *si = map(lambda x: int(x) - 1, input().split())

    smi[i] = si

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

def emitable(bit_pattern, i):
    si = smi[i]
    px = pi[i]
    py = 0

    for s in si:
        py += (bit_pattern & (2 ** s)) >> s

    return px == (py % 2)

count = 0

for bi in range(2 ** n):
    if all(emitable(bi, i) for i in range(m)):
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
K = []
S = []
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(' ')))
ans = 0
for i in range(2**n):
    light = 0
    for j in range(m):
        sw = 0
        for s in S[j]:
            if (i>>(s-1))&1:
                sw += 1
        if sw%2 == p[j]:
            light+=1
    if light == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
S = [0]*M
answer = 0

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

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

for i in range(2**N):
    mb = '0' + str(N) + 'b'
    bi = format(i, mb)
    count = 0
    for j in range(M):
        on = 0
        for k in range(S[j][0]):
            on += int(bi[-S[j][k+1]])
        if on%2 == P[j]:
            count += 1
    if count == M:
        answer += 1

print(answer)

Submission status: Accepted

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

ans = 0
str = '{:0'+str(n)+'b}'
for i in range(2**n):
  s = list(map(int, str.format(i)))
  b = True
  for j in range(m):
    if sum([x & y for x, y in zip(s, l[j])]) % 2 != p[j]:
      b = False
  if b:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None


class UnionFind:
    def __init__(self, n):
        self.r = [-1]*(n+1)

    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x,y = y,x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -1 * self.r[self.root(x)]


class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M = mulinputs()
    ks, ss, ps = [], [], []
    for _ in range(M):
        k, *s = list(mulinputs())
        ks.append(k)
        ss.append(s)
    ps = list(mulinputs())

    cnt = 0
    for n in range((1<<N)):
        state = [0] * N
        for j in range(N):
            state[j] = (n&(1<<j))>>j
        is_light = True
        for j in range(M):
            icnt = 0
            for s in ss[j]:
                icnt += state[s-1]
            if icnt%2 != ps[j]:
                is_light = False
                break
        if is_light:
            cnt+=1

    # 出力
    print(cnt)

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):
    s = i
    b = [0]*N
    for j in range(N):
        if s >= (2**(N-j-1)):
            s -= 2**(N-j-1)
            b[j] = 1
    for j in range(M):
        on = 0
        for k in range(ks[j][0]):
            if b[ks[j][k+1]-1] == 1:
                on += 1
        if on%2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

from itertools import product
iterator=product(range(p),repeat=n)

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

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

ans=0
for idxs in iterator:
    tmp1=0
    for i in range(m):
        tmp2=0
        for j in s[i]:
            tmp2+=idxs[j-1]
        if tmp2%2==p[i]:
            tmp1+=1
    if tmp1==m:
        ans+=1
print(ans)

Submission status: Accepted

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

from itertools import product

ans = 0
for a in product([0,1],repeat=n):
    for j,l in enumerate(li):
        t = 0
        for k in l[1:]:
            t += a[k-1]
        t %= 2
        if t != p[j]:break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
s = [[int(x) - 1 for x in input().split()][1:] for i in range(m)]
p = [int(x) for x in input().split()]
print(sum(1 for mask in range(1 << n) if all(sum((mask >> bulb) & 1 for bulb in s[i]) % 2 == p[i] for i in range(m))))

Submission status: Accepted

Solution code:
from itertools import product, repeat
import numpy as np

input_row = lambda : [int(_) for _ in input().split(' ')]

N, M = input_row()
C = np.zeros((M, N), dtype=np.int32)

for i in range(M):
    s = np.array(input_row()[1:]) # ignore k
    C[i, s-1] = 1 # s_ to zero index.

p = input_row()

all_on_num = 0
for S_ in product(*(repeat([1, 0], N))):
    S = np.array(S_)

    L = C.dot(S)%2 == p

    if len(L[L == True]) == M:
        all_on_num += 1
print(all_on_num)

Submission status: Accepted

Solution code:
from itertools import product, repeat
import numpy as np

input_row = lambda : [int(_) for _ in input().split(' ')]

N, M = input_row()
C = np.zeros((M, N), dtype=np.int32)

for i in range(M):
    s = input_row()[1:]
    for s_ in s:
        C[i, s_-1] = 1

p = input_row()

all_on_num = 0

for S_ in product(*(repeat([1, 0], N))):
    S = np.array(S_)

    L = C.dot(S)%2 == p
    L_on = L[L == True]
    all_on = len(L_on) == M

    if all_on:
        all_on_num += 1
print(all_on_num)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

#bit全部作ってる
#bit = [i>>j&1 for j in range(N)]

n,m=MI()
lights=[LI() for _ in range(m)]
p_list=LI()

bit_list=[]
count=0
for i in range(2**n):
    bit = [i>>j&1 for j in range(n)]
    flag=0
    for j in range(m):
        ki=lights[j][0]
        onswitch=0
        for k in range(1,ki+1):
            si=lights[j][k]
            onswitch+=bit[si-1]
        if onswitch%2!=p_list[j]:
            flag+=1
    if flag==0:
        count+=1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(1<<N):
    ri_count = 0
    for j in range(M):
        sw_count = 0
        for l in range(k[j]):
            if i>>(s[j][l]-1) & 1:
                sw_count += 1
        if sw_count%2 == p[j]:
            ri_count += 1
    if ri_count == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

n, m = map(int, input().split(' '))
k = []
s = []
for i in range(m):
    a = list(map(int, input().split(' ')))
    k.append(a[0])
    s.append(a[1:])
p = list(map(int, input().split(' ')))
ans = 0
for i in range(2**n):
    ri_cnt = 0
    for j in range(m):
        sw_cnt = 0
        for l in range(k[j]):
            if (i >> (s[j][l]-1)) & 1:
                sw_cnt += 1
        if sw_cnt % 2 == p[j]:
            ri_cnt += 1
    if ri_cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 93 C - Switches
N,M = map(int,input().split())
K = []
S = []
for _ in range(M):
    s = list(map(int,input().split())) 
    K.append(s[0])
    # 0-indexed
    s = [i-1 for i in s]
    S.append(s[1:])
P = list(map(int,input().split()))

ans = 0
for i in range(1<<N):
    swiches = [0]*N
    for j in range(N):
        mask = 1<<j
        # j 番目のスイッチが on のとき
        if i & mask != 0:
            swiches[j] = 1
        # j 番目のスイッチが off のとき
        else:
            continue

    # on の電球をカウント
    cnt_light = 0
    for m in range(M):
        cnt_swich = 0
        for s in S[m]:
            if swiches[s] == 1:
                cnt_swich += 1
        if cnt_swich%2 == P[m]:
            cnt_light += 1
    if cnt_light == M:
        ans += 1
print(ans)

Submission status: Accepted

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

ans=0

for i in range(2**n):
    All_On=True
    for j in range(m):
        k_on=0
        for k in range(1,lamp[j][0]+1):
            if i>>lamp[j][k]-1 & 1:
                k_on+=1
        if k_on%2!=p[j]:
            All_On=False
            break
    if All_On:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#import math
import itertools
#import numpy as np
#from collections import deque


INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    cnct=[]
    for i in range(m):
        temp=LIST()
        temp=temp[1:]
        cnct.append(temp)
    ps=LIST()
    ans=0
    
    for bit in range(2**n):
        check=[0]*m
        for i in range(n):
            if (bit>>i)&1:
                for k in range(m):
                    if i+1 in cnct[k]:
                        check[k]+=1
        
        flg=True
        for k in range(m):
            if check[k]%2!=ps[k]:
                flg=False
        
        if flg:
            ans+=1
    
    print(ans)


if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
mat = [[int(i) for i in input().split()] for k in range(M)]
p = [int(i) for i in input().split()]
switch = [0]*N
O = [0]*M
L = [False]*M
ans = 0

for i in range(2 ** (N)):
    switchsub = list(format(i,'b'))
    for j in range(len(switchsub)):
        switch[-j-1] = switchsub[-j-1]
    for j in range(N):
        if(switch[j] == "1"):
            for k in range(M):
                for l in range(1,len(mat[k])):
                    if(mat[k][l] == j+1):
                        O[k] += 1
    for j in range(M):
        if(O[j] % 2 == p[j]):
            L[j] = True
    if(False not in L):
        ans += 1
        switch = [0]*N
        O = [0]*M
        L = [False]*M
    if(False in L):
        switch = [0]*N
        O = [0]*M
        L = [False]*M

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
#coding: utf-8

N, M = (int(x) for x in input().split())

S = []
for i in range(M):
    S.append([int(x)-1 for x in input().split()][1:])
P = [int(x) for x in input().split()]

ret = 0
for bit in range(2**N):
    on = [i for i in range(N) if bit & (1 << i)]
    if all(sum(1 for switch in S[i] if switch in on) % 2 == P[i] for i in range(M)):
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
#coding: utf-8

N, M = (int(x) for x in input().split())

S = []
for i in range(M):
    items = [int(x)-1 for x in input().split()]
    S.append(items[1:])

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

ret = 0
for bit in range(2**N):
    on = [i for i in range(N) if bit & (1 << i)]
    ok = True
    for i in range(M):
        s = S[i]
        p = P[i]
        if sum(1 for switch in s if switch in on) % 2 != p:
            ok = False
            break
    if ok:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
# author:  Taichicchi
# created: 16.09.2020 23:07:07

import sys

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

k = []
s = []

for i in range(M):
    _k, *_s = map(int, input().split())
    k.append(_k)
    s.append(_s)

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


for i in range(2 ** N):
    sw = [0 for _ in range(N)]
    for j in range(N):
        if i >> j & 1:
            sw[j] = 1

    for m in range(M):
        mod = 0
        for switch in s[m]:
            mod += sw[switch - 1]
        if mod % 2 != p[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    sw=[]
    on=0
    for j in range(n):
        sw.append(i>>j & 1)
    for k in range(m):
        if (sum( [sw[ks[k][j+1]-1] for j in range(ks[k][0])] ))%2 == p[k]:
            on +=1
    if on==m:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
switch = [0] * N
pattern = 2 ** N
ans = 0
for i in range(M):
  temp = input().split()[1:]
  for j in temp:
    switch[int(j) - 1] += (1 << i )
  
p = list(map(int, input().split()))
pbin = 0
temp = 1
for i in p:
  pbin += i * temp
  temp *= 2

for i in range(pattern):
  temp = 0
  j = 0
  while i > 0:
    if i & 1 == 1 :
      temp = temp ^ switch[j]
    j += 1
    i = i >> 1
  if pbin == temp:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def light(l,i):
    k=1<<(i-1)
    if l&k:
        return 1
    else:
        return 0

N, M = map(int,input().split())
s=list()
for j in range(0,M):
    s.append(0)
for j in range(0,M):
    s[j]=list(map(int,input().split()))
p=list(map(int,input().split()))

a=0
for l in range(0,1<<N):
    b=0
    for j in range(0,M):
        c=0
        for i in range(1,s[j][0]+1):
            c+=light(l,s[j][i])
        if c%2==p[j]:
            b+=1
    if b==M:
        a+=1
print(a)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
s=[]
ans=0
for i in range(m):
  kk, *ss=map(int,input().split())
  k.append(kk)
  s.append(ss)
p=list(map(int,input().split()))
for i in range(2**n):
  tmp=[]
  for j in range(n):
    if (i>>j)&1:
      tmp.append(j+1)
  for j in range(m):
    if len(set(tmp)&set(s[j])) % 2 != p[j]:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
k, s = [], []
for i in range(m):
  inp = list(map(int, input().split()))
  k_, s_ = inp[0], inp[1:]
  k.append(k_)
  s.append(s_)
p = list(map(int, input().split()))
ans = 0
for bit in range(1<<n):
  flg = True
  for i in range(m):
    cnt = 0
    for e in s[i]:
      e -= 1
      if bit & 1<<e: cnt += 1
    if cnt%2 != p[i]: flg = False
  if flg: ans += 1
print(ans)

Submission status: Accepted

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

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

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

    ans = 0
    for i in range(2**N, 2**(N+1)):
        b = bin(i)[3:]
        t = [0] * M
        for j, sj in enumerate(s):
            for k, bi in enumerate(list(b)):
                if bi == '1' and k+1 in sj:
                    t[j] += 1
            if t[j] % 2 != p[j]:
                ans -= 1
                break
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
K = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    bit = [i>>j&1 for j in range(n)]
    for j,k in enumerate(K):
        if p[j] != sum([bit[l-1] for l in k])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#
# abc128 c
#

import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


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

    ans = 0
    for bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)):
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


def resolve():
    global N, M, KS, P
    N, M = map(int, input().split())
    KS = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))

    ONS = deque()
    print(dfs(0, ONS))


def dfs(n, T):
    if n == N:
        onm = 0
        for i, ks in enumerate(KS):
            k, s = ks[0], ks[1:]
            onsn = 0
            for t in T:
                if t in s:
                    onsn += 1
            if onsn % 2 != P[i]:
                break
            else:
                onm += 1
        if onm == M:
            return 1
        else:
            return 0

    ans = 0
    T.append(n+1)
    ans += dfs(n+1, T)
    T.pop()
    ans += dfs(n+1, T)
    return ans


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
Switch = []
for i in range(M):
    Swi = list(map(int,input().split()))
    S = Swi[0]
    Switch.append(Swi[1:S+1])
Plist = list(map(int,input().split()))
Ans = 0
L = [0,1]
c_list = list(itertools.product(L, repeat=N))
for comb in c_list:
    for i in range(M):
        Jud = 0
        Swi = Switch[i]
        for j in Swi:
            Jud += comb[j-1]
        if Jud%2 != Plist[i]:
            break
        elif i == M-1:
            Ans += 1
print(Ans)

Submission status: Accepted

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

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

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

ans=0
for i in range(2**N):
  isOK=True
  for j in range(M):
    stat=0
    for k in l[j]:
      k-=1
      if i&(1<<k):
        stat=(stat+1)%2
    if stat!=p[j]:
      isOK=False
  if isOK:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
K_and_Ss = []
for i in range(M):
    data = list(map(int,input().split()))
    K_and_Ss.append(data)
Ps = list(map(int,input().split()))

flag = False
x = 2**N
sum = 0
for i in range(x):
    for j in range(M): #j番目の電球がついているかを判定
        count = 0
        if flag:
            flag = False
            break
        for k in range(len(K_and_Ss[j])-1):
            if (i >> (K_and_Ss[j][k+1]-1) & 1) == 1:
                count += 1
            if k ==len(K_and_Ss[j])-2 and count % 2 == Ps[j]:
                flag = False
                if j == M-1:
                    sum += 1
            if k ==len(K_and_Ss[j])-2 and count % 2 != Ps[j] and j != M-1:
                flag = True
print(sum)