note: 競プロ初心者にとっては、公式解説 の方法を身につける方が有益だと思います。

公式解説の 解法2. bit 全探索の要領で構成する を高速に行うのに相当する方法です。

---

pdep (parallel bits deposit) という CPU 命令があります。これは、二つの整数 src, mask を引数に取り、各 bit が以下のように定まる値 dst を返します。ただし、bit は下（右、小さい方）から数え、0-indexed とします。

• mask の \(i\) bit 目が 0 のとき、dst の \(i\) bit 目は 0 である
• mask の \(i\) bit 目が 1 のとき、dst の \(i\) bit 目は src の \(j\) bit 目である
  • ここで、mask の \(i\) bit 目が \(j\) 個目の 1 であるとする

言い換えると、mask で bit が立っている場所に、src の下位 bit たち（mask の立っている bit の個数ぶん）を順にばら撒くようなイメージです。

例：

src:  0000_0000_0000_0000_0000_1010_0101_0000
mask: 0100_1001_1001_1010_0100_0100_0101_0100
       1   0  1 0  0 1 0   1    0    0 0  0
dst:  0100_0001_0000_1000_0100_0000_0000_0000

さて、今回の問題では、0...00, 0...01, 0...10, …, 1...11 を、入力で与えられた n で bit が立っている場所にばら撒けばよいです。

例 (\(n = 11_{(10)} = 1011_{(2)}\))：

000 -> 0000
001 -> 0001
010 -> 0010
011 -> 0011
100 -> 1000
101 -> 1001
110 -> 1010
111 -> 1011

よって、\(n\) の立っている bit の個数を \(m\) として、\(0\) 以上 \(2^m\) 未満の各整数 \(i\) に対して、pdep(src = i, mask = n) を計算すればよいとわかります。

• 提出 #34956314, C++
• 提出 #34956469, Rust

---

余談

pdep の逆処理、すなわち dst と mask から src を得る命令は、pext (parallel bits extract) と呼ばれています。pext(src, mask) は、src の bit のうち、mask で bit が立っているものを下位に集める命令です。

src:  0100_0001_0000_1000_0100_0000_0000_0000
mask: 0100_1001_1001_1010_0100_0100_0101_0100
       1   0  1 0  0 1 0   1    0    0 0  0
dst:  0000_0000_0000_0000_0000_1010_0101_0000

pdep や pext は、環境によっては使えない命令なので、使おうとする場合は注意しましょう。AtCoder の環境や、wandbox, Rust Playground の環境では使えるようです。

CPU 命令として用意されていない場合でも、ワードサイズ \(w\) に対し、\(O(\log(w)^2)\) 時間などで計算するアルゴリズムがあります。また、mask が予めわかっている場合であれば、前処理 \(O(\log(w)^2)\) 時間、クエリあたり \(O(\log(w))\) 時間でも計算できます。

命令名の parallel は、ループで各ビットを処理する（公式解説解法 2 のように）のではなく、複数のビットを並列で処理することに由来していそうです。bit-level parallelism とかで調べるといいかもしれません。C 言語での実装例

ビット並列手法に関する記事 も書きました。

---

追記

ループの上限を求める際に、pext(n, n) を使えばいいと指摘を受けました。賢いと思いました。