Problem: 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?

Submission attempts (in order):



def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        for i in range(m): 
            cnt = 0
            for v in s[i]: 
                if ( bit & 1 << (v - 1) ): 
            if cnt % 2 != p[i]:
                ok = False
        if ok: 
            res += 1

    print(res)

if __name__ == "__main__":
    main()



def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        
        
        for i in range(m):
            cnt = 0
            for v in s[i]:
                
                if bit & (1 << v):
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False

        if ok: 
            res += 1

    print(res)



if __name__ == "__main__":
    main()




def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        for i in range(m): 
            cnt = 0
            for v in s[i]: 
                if ( bit & 1 << (v - 1) ): 
            if cnt % 2 != p[i]:
                ok = False
        if ok: 
            res += 1

    print(res)



if __name__ == "__main__":
    main()



def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp_k, *tmp_s = list(map(int, input().split()))
        k.append(tmp_k); s.append(tmp_s)
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        
        
        for i in range(m):
            cnt = 0
            for v in s[i]:
                
                if bit & (1 << v):
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False

        if ok: 
            res += 1

    print("res : ", res)



if __name__ == "__main__":
    main()


def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp = list(map(int, input().split()))
        s.append(tmp[1:]); k.append(tmp[0])
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        for i in range(m): 
            cnt = 0
            for v in s[i]: 
                if ( bit & 1 << (v - 1) ): 
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False
        if ok: 
            res += 1

    print(res)

if __name__ == "__main__":
    main()

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted