Roomshare

スイッチの列を以下のように定義します。

• 番号 $i$ のスイッチの列は、長さが $N$ の 0, 1 からなる列であり、$A_{i,1}, A_{i,2}, … A_{i,T_i}$ 番目の値が 1 であり、それ以外は 0 である。

番号 $i$ のスイッチを押すという動作は、各電球の状態 $S$ に対して 番号 $i$ のスイッチの列と XOR をとるという行為と同じです。

したがって、この問題は以下のように言い換えることができます。

• $S_i$ の状態からいくつかのスイッチの列と XOR をとることによってすべての値を 1 にできるか？

この問題は、スイッチの列を行列とみなし、掃き出し法などによって簡約化をすることによって解くことができます。
具体的には、行列の簡約化によって、線形独立な $N$ 本の行ベクトルを取り出すことによって高速に判定を行うことができます。

よって、この問題を全体で $O(N(M+Q))$ で解くことができ十分高速です。