ABC128 C - Switches - ツバサの備忘録

解法

スイッチと電球の個数がとても少ないので、 $j$ 番目の電球に対して機能するスイッチの情報、およびどのスイッチを押すか、という状態をどちらもbitを利用して、int型の変数1つで持つことができます。
スイッチを押すパターンは $2^{N}$ 通りで、多くても1024通り程度です。今調べるパターンを $i$ とし、このときに全ての電球が付くかどうかを調べ、 $i$ について全探索すれば、答えを求めることができます。
$i$ のパターンのときに、 $j$ 番目の電球が付くかどうかを調べます。
こうなるのは、 $j$ 番目の電球に対して機能するスイッチの状態を $s_{j}$ としたときに、 $i$ と $s_{j}$ 両方で立っているビットの個数を2で割った数が、 $p_{j}$ と一致した場合です。
両方で立っているビットを取り出すのはAND演算を利用すればいいので、 $i \ and \ s_{j}$ となります。
この値について、立っているビットの個数を調べるのも、ビット演算を利用すると効率よく計算できます。