ABC128 C - Switches

f:id:tkr987:20200625223812p:plain

f:id:tkr987:20200625223922p:plain

任意の電球1個について「配線を辿ってスイッチの個数のmod2がpかどうか」は $O(10)$ で判定できる。電球が10個しかないので、任意のスイッチ1パターンに対して電球全て調べても $O(10) \times 10 = O(100)$ で処理できる。

なお、スイッチがOFFのときはカウントしてはいけない。

if (NT_NyaaBit::Test(i, k) == e[k]) ++count;

と書きたくなるが、これだとスイッチOFFのときもカウントしてしまうため

if (NT_NyaaBit::Test(i, k) == 1 && e[k]) ++count;

と書く必要がある。スイッチパターンが全部で $2^{10}$ しかないので、全体計算量 $O(M2^N)$ で求まる。

7K4B blog