公式

K - Or Set 解説 by Magentor 印刷ページ

操作をしたときに得られる最終的な \(X\) の値を \(Y\) とします。

実は \(Y\) として考えられるもののうち、\(Y\) を \(2\) 進法で表記したときの \(2^i\) の位が \(0\) であるものは高々 \(1\) つしか存在しません。

略証 \(Y\) の \(2^i\) の位を \(0\) にすることを考えます。

\(A_j\) の \(2^i\) の位が \(1\) であるようなときに \(X\) を置き換える操作が行われた場合、明らかに条件を満たしません。

ここで、\(A_j\) の \(2^i\) の位が \(0\) であるようなとき、必ず \(X\) を置き換える操作が行われることを考慮すると、\(Y\) として考えられるものが \(2\) 通り以上存在するためには、\(A_j\) の \(2^i\) の位が \(1\) であるようなときに \(X\) を一回以上置き換えることができる必要があります。

この \(2\) つの事実は明らかに矛盾するので、題意が示されます。

よって、\(i=0,1,\dots,M-1\) について、\(2^i\) の位が \(0\) であるような \(Y\) を実際に求めれば良いです。

これは、\(A_j\) の \(2^i\) の位が \(0\) であるようなものを並べた後、\(A_j\) の \(2^i\) の位が \(1\) であるようなものを並べれば良いです。

よって、この問題を \(O(NM)\) で解くことができました。

投稿日時:
最終更新: