F - Another Long Sequence Inversion 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

非負整数 L,R,X が二進法で与えられます。長さ R-L+1 の整数列 (L \oplus X,(L+1)\oplus X, \dots, R\oplus X) の転倒数を二進法で求めてください。

ただし、\oplus はビットごとの排他的論理和を表します。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

転倒数とは 数列 B=(B_1,B_2,\dots, B_M) の転倒数とは、整数の組 1 \leq i \lt j \leq M であって B_i \gt B_j を満たすものの個数です。
ビットごとの排他的論理和とは 非負整数 A,B のビットごとの排他的論理和 (XOR) A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、 3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101=110)。

制約

  • 1 \leq T \leq 2 \times 10^5
  • 0 \leq L \leq R \lt 2^{2 \times 10^5}
  • 0 \leq X \lt 2^{2 \times 10^5}
  • 入力は全て整数
  • T は 十進法で与えられる
  • L,R,X は二進法で与えられ、先頭に余分な 0 を含まない（ただし 0 は 1 桁の整数とみなす）
  • 1 つの入力ファイルに含まれる R の二進法での桁数の総和は 2 \times 10^5 以下
  • 1 つの入力ファイルに含まれる X の二進法での桁数の総和は 2 \times 10^5 以下

部分点

追加の制約 T \leq 3000, R \lt 2^{30}, X \lt 2^{30} を満たすデータセットに正解した場合は 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

L R X

出力

T 行出力せよ。i 行目には i 個目のテストケースに対する答えを出力せよ。

入力例 1

3
101 1000 10
1101 10111010 0
1000110 1110011011101 100011110010

出力例 1

10
0
11100100001101111010100

1 つ目のテストケースについて、L,R,X をそれぞれ十進法で表記すると L=5,R=8,X=2 です。(5\oplus 2, 6\oplus 2, 7\oplus 2, 8\oplus 2)=(7,4,5,10) なので求めるべき転倒数は 2 です。