\(A=\{0\},N=1,w=1\) からスタートすることにします． ここで \(w\) は，\(\max(A)<2^w\) を満たす整数です．

以下の \(2\) つの操作が実現できるので，これらを組み合わせれば問題が解けます．

• \(N\) を \(2N\) にする．
• \(N\) を \(N-1\) にする．\(w\) に \(1\) を足す．

これらの操作を具体的に示します．

まず，\(2N\) を達成する方法としては，\(2^w-1\) を \(A\) に追加すればよいです．

\(N-1\) を達成するためには，まず \(A\) の条件を満たす部分列のうち，極小なものを任意にとります． そして，その部分列に含まれる値に \(2^w\) を足します． あとは \(w\) を \(1\) 増加させます． この操作を行う前と後では，最初に選んだ部分列でのみ，「AND が \(0\) か否か」が変化することが確認できます．

解答例(c++)