【競技プログラミング】AtCoder Beginner Contest 128_C問題

# 問題

https://atcoder.jp/contests/abc128/tasks/abc128_c

## 要約


1. N個のスイッチ（on/off状態を持つ）とM個の電球がある。
2. スイッチには1からN、電球には1からMの番号がついている。
3. 各電球iは以下の条件で点灯する：
   - ki個のスイッチに接続されている
   - 接続されたスイッチのうち、onになっているスイッチの数を2で割った余りがpiに等しい時
4. 全ての電球が同時に点灯するようなスイッチのon/offの組み合わせの数を求める。

変数情報：
- N: スイッチの総数
- M: 電球の総数
- ki: 電球iに接続されているスイッチの数
- si1, si2, ..., siki: 電球iに接続されているスイッチの番号
- pi: 電球iが点灯するための条件（接続されたスイッチのon数を2で割った余り）


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

# アプローチ
ビット全探索を用いて、全てのスイッチの組み合わせを効率的に生成し、各組み合わせに対して全ての電球の点灯条件を確認する。

1. 全ての可能なスイッチの組み合わせを調べる必要があるため、ビット全探索を使用。
1. 各組み合わせに対して、全ての電球の点灯条件を確認する。
   そのため、二重ループ構造（ビット全探索のループと電球の確認ループ）を使用。



# 解法手順

1. 入力を受け取る：
   - スイッチの数Nと電球の数Mを取得する
   - 各電球に接続されているスイッチの情報を2次元リストとして保存する
   - 各電球の点灯条件pを取得する

2. ビット全探索を実行する：
   - 0から2^N-1までの数をビットパターンとして使用する

3. 各ビットパターンに対して以下の処理を行う：
   - オンになっているスイッチのリストを作成する
   - 全ての電球に対して点灯条件を確認する：
     - 電球に接続されているスイッチのうち、オンになっているものの数を数える
     - その数を2で割った余りが点灯条件pと一致するか確認する
   - 全ての電球が点灯条件を満たす場合、カウンターをインクリメントする

4. 全てのパターンをチェックした後、カウンターの値を出力する


# ACコード
```python:ac.py
def io_func():
    # スイッチの数Nと電球の数Mを取得
    n, m = map(int, input().split())
    
    # 各電球に接続されているスイッチの情報を2次元リストとして保存
    lights = [list(map(int, input().split()))[1:] for _ in range(m)]
    
    # 各電球の点灯条件pを取得
    p = list(map(int, input().split()))
    
    return n, m, lights, p

def solve(n, m, lights, p):
    res = 0  # 条件を満たす組み合わせの数をカウントする変数
    
    # ビット全探索を実行
    for bit in range(1 << n):
        light_on = []  # オンになっているスイッチのリスト
        
        # オンになっているスイッチを特定
        for i in range(n):
            if (bit >> i) & 1:
                light_on.append(i + 1)
        
        flag = True  # 全ての電球が条件を満たすかどうかのフラグ
        
        # 全ての電球に対して点灯条件を確認
        for i in range(m):
            cnt = 0  # オンになっているスイッチの数
            for light in lights[i]:
                if light in light_on:
                    cnt += 1
            
            # 点灯条件を満たしているか確認
            if cnt % 2 != p[i]:
                flag = False
                break
        
        # 全ての電球が条件を満たす場合、カウンターをインクリメント
        if flag:
            res += 1
    
    return res

# メイン処理
n, m, lights, p = io_func()
result = solve(n, m, lights, p)
print(result)

###
# 変数の意味:
# n: スイッチの数
# m: 電球の数
# lights: 各電球に接続されているスイッチの情報を格納した2次元リスト
# p: 各電球の点灯条件を格納したリスト
# res: 条件を満たす組み合わせの数
# bit: ビット全探索に使用する変数
# light_on: 現在のビットパターンでオンになっているスイッチのリスト
# flag: 全ての電球が条件を満たすかどうかを示すフラグ
# cnt: 各電球に対して、オンになっているスイッチの数

# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
#    - ビット全探索を使用して全てのスイッチの組み合わせを生成
#    - 各組み合わせに対して、全ての電球の点灯条件を確認
#    - 条件を満たす組み合わせの数をカウント
# 3. 結果を出力する
####################################################################################
# このコードの計算量は O(2^N * M * K) 
# - N はスイッチの数
# -- ビット全探索で 2^N 回のループを行います。
# - M は電球の数
# -- 各ループで M 個の電球をチェックします。
# - K は各電球に接続されているスイッチの平均数
# -- 各電球のチェックで平均 K 個のスイッチを確認します。
####################################################################################

```

# 解法整理

1. 集合論と組み合わせ論
   - スイッチの集合 S = {1, 2, ..., n} を考える。
   - 全ての可能なスイッチの組み合わせ（部分集合）を探索している。
   - これは $2^n$ 通りの組み合わせを意味する。

2. 二進法（2進数）とビット演算
   - `for bit in range(1 << n):` の部分で、0から $2^n - 1$ までの数を2進数で表現している。
   - `1 << n` は $2^n$ を表す。これは1を2進数で左に n ビットシフトすることで得られる。
   - `(bit >> i) & 1` の部分で、bit の i 番目のビットが1かどうかを判定している。
     - `bit >> i` は bit を右に i ビットシフトする操作。
     - `& 1` は最下位ビットとの論理積を取る操作。

3. 剰余演算（偶奇判定）
   - `cnt % 2 != p[i]` の部分で、オンになっているスイッチの数の偶奇を判定している。
   - $a \equiv b \pmod{2}$ という合同式で表現できる。

4. 論理演算
   - `flag` 変数を使用して、全ての条件を満たすかどうかを論理的に判定している。
   - これは $\land$ (AND) 演算子を用いて $\bigwedge_{i=1}^m (条件_i)$ と表現できる。

5. 2次元配列（行列）
   - `lights` は $m \times k_i$ の2次元配列（ただし $k_i$ は各行で異なる可能性がある）。
   - これは数学的には $m$ 個の集合 $L_i \subseteq S$ $(i = 1, 2, ..., m)$ と考えられる。

6. 計数問題
   - 条件を満たす組み合わせの数を数え上げている。
   - これは $|\{x \in \mathcal{P}(S) : 条件(x)\}|$ と表現できる。ここで $\mathcal{P}(S)$ は S のべき集合。

7. 時間計算量
   - このアルゴリズムの時間計算量は $O(2^n \cdot m \cdot \bar{k})$ である。
   - $\bar{k}$ は各電球に接続されているスイッチの平均数。

## ループ変数とビット演算の説明

- 外側のループ `for bit in range(1 << n):` は、0から $2^n - 1$ までの全ての整数を生成する。
  各整数 `bit` は、n個のスイッチのオン/オフの状態を表す。

- 内側のループ `for i in range(n):` は、各スイッチの状態を確認する。
  `(bit >> i) & 1` の操作で、i番目のスイッチがオンかオフかを判定する。
  - `bit >> i` は `bit` を2進数表記で右に i ビットシフトする。これにより、i番目のビットが最下位ビットになる。
  - `& 1` は最下位ビットとの論理積を取る。結果が1ならそのスイッチはオン、0ならオフとなる。

- `light_on` リストには、オンになっているスイッチの番号が格納される。
  これにより、各ビットパターンに対応するスイッチの組み合わせが得られる。