\(K=1\) のときの問題はグレイコードとして有名です．

以下，\(K \geq 2\) を考えます． まず，\(K\) が偶数の場合，答えは必ず不可能です． これは，すべての数の popcount の偶奇が一定になってしまうためです．

また，\(K=N\) の場合も明らかに不可能です．

それ以外の場合は可能です． 以下，実際に構築を行うことでそれを示します．

\(N\) bit の XOR の基底であって，popcount が \(K\) になる値のみからなるものを取ることができます． これを適当にひとつとり，\(z_1,z_2,\cdots,z_N\) とおきます．

また，\(N\) bit のグレイコード（つまり隣接項がちょうど \(1\) bit だけ異なる順列）を求め，\(a_0,a_1,\cdots,a_{2^N-1}\) とおきます．

ここで，\(b_i\) を以下のようにして定めます．

• \(a_i\) の bit が \(1\) になっている位置を \(j_1,j_2,\cdots\) として，\(b_i=z_{j_1} \oplus z_{j_2} \oplus \cdots\) とする．

このとき \(b\) は元の問題の答えになっています． まず，隣接項の XOR は \(z\) のいずれかの要素になっているため，隣接項が \(K\) bit だけ異なるという条件を満たします． また，\(z\) が基底であったことから，\(b\) は順列になります．

計算量は \(O(N 2^N)\) です．

解答例(c++)