ABC128-C Switches 解説 - neboccoのブログ

$ O(M ^ 2) $ (一般の $N, M $ については $ O(NM ^ 2) $ ) で解きます。

問題

概要

$N$ 個のスイッチと $M $ 個の電球がある。$i$ 番目のスイッチ $ (1\leq i\leq N) $ は $ k _ i $ 個の電球 $s _ {i1},s _ {i2},\ldots,s _ {ik _ i}(1 \leq s _ {ij} \leq M)$ の状態を切り替える。全ての電球を ON にするスイッチの ON / OFF の決め方は何通りか？

解法

editorial解は素朴な全探索ですが、線形代数を用いて計算量を改善します。 (大学一年生レベルの線形代数の知識が必要になります。)

$N$ 次元ベクトル $\bm{x}$ 、$N \times M $ 行列 $A$ をそれぞれ

$$ \begin{aligned} \bm{x} _ i &= \begin{cases} 1 & \text{(スイッチ $i$ が ON)} \\ 0 & \text{(OFF)} \end{cases} \\ A _ {ij} &= \begin{cases} 1 & \text{(電球 $i$ がスイッチ $j$ の影響を受ける)} \\ 0 & \text{(受けない)} \end{cases} \end{aligned} $$

と定義します。求める答えは入力で与えられる $\bm{p}$ を用いて、 $\bm{x}$ についての

\[ A\bm{x} \equiv \bm{p} \quad (\mathrm{mod}\:2) \]

の解の個数に等しいです。

この解は拡大係数行列 $(A\,|\,\bm{p})$ に掃き出し法を行うことで求めることができます。また、解の自由度を $r$ とすると $r = N - \mathrm{rank}(A\,|\,\bm{p})$ です。つまり $r$ 個のスイッチについては ON / OFF を自由に決定することができるので、解の個数は $2 ^ r$ です。ただし、係数行列部分が全て $0$ なのに定数項が $0$ でないような行が存在した場合は 解なし となるため注意してください。計算量は $O(NM ^ 2)$ です。

さらに、演算が $\text{mod}\:2$ 上で行われること、 $N$ がワードサイズに収まる $(\leq 32)$ ことから、以下の実装では $A$ をビットで表現し、掃き出し法をビット演算によって行っています。

$$ \begin{array}{ccc} A = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{pmatrix} & \longrightarrow & A = \begin{pmatrix} \mathrm{01101} _ {(2)} \\ \mathrm{00011} _ {(2)} \\ \mathrm{10010} _ {(2)} \\ \mathrm{01100} _ {(2)} \\ \mathrm{01001} _ {(2)} \\ \mathrm{11100} _ {(2)} \\ \end{pmatrix} = \begin{pmatrix} 13 \\ 3 \\ 18 \\ 12 \\ 9 \\ 28 \end{pmatrix} \end{array} $$

これにより計算量は $O(M ^ 2)$ になっています。 $N$ が大きい場合にも、Pythonの多倍長整数やC++のbitsetを用いて同様の工夫を行なうことで、定数倍を大きく改善することができます。

実装

提出コード(Python)

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

 # 行列 A の構築
A = [0] * M
for i in range(M):
  for x in s[i]:
    A[i] |= 1 << (N - x)

# 拡大
for i in range(M):
  A[i] = A[i] << 1 | p[i]

# 掃き出し法
# mod2 なので XOR でよい
for i in range(M):
  # 最も高い bit が立っている行を探す
  for j in range(i+1, M):
    if A[i] < A[j]:
      A[i], A[j] = A[j], A[i]
  if A[i] == 0:
    break
  # 掃き出す
  msb = 1 << (A[i].bit_length() - 1)
  for j in range(M):
    if j == i:
      continue
    if A[j] & msb:
      A[j] ^= A[i]

# 係数が全て0 かつ 定数項が1 の行がある <=> 解なし
if 1 in A:
  ans = 0
else:
  rank = sum(x > 0 for x in A)
  ans = pow(2, N - rank)

print(ans)