【競プロ】過去問精選100問「AtCoder Beginner Contest 128 C - Switches」解法

def main():
    N, M = map(int, input().split(" "))
　　
    # 各電球と繋がっているスイッチをリストに格納 
    key_swiches = []
    for _ in range(M):
        tmp = [i for i in map(int, input().split(" "))]
        tmp = tmp[1:]
        key_swiches.append(tmp)
    
    # pをリストで取得
    p = [i for i in map(int, input().split(" "))]

    # 全スイッチの一覧を作成
　　swiches = [i for i in range(1, N + 1)]
　　
    # ビット全探索
    ans = 0
    for i in range(2 ** N):
        tmp = swiches.copy()
　　　　 # offのスイッチをtmpから削除
        for j in range(N):
            if not (i >> j) & 1:
                tmp.remove(swiches[j])

　　　　 # 各電球ごとに条件を満たすか確認
        for m in range(len(key_swiches)):
            count = 0
            for l in range(len(key_swiches[m])):
                if key_swiches[m][l] in tmp:  # 電球と繋がっているスイッチがonかどうか確認
                    count += 1
            if count % 2 != p[m]:  # pの条件を満たすか確認
                break
        else:
            ans += 1  # foo loopが一度もbreakしなかったらansに1を足す

    print(ans)


if __name__ == '__main__':
    main()