L ≤ x ≤ y ≤ R

「\(L,R\) が入力として与えられ、整数の組 \((x,y)\) \((L\le x\le R,L\le y\le R)\) であって、指定された条件を満たすものの個数を求める問題」を割と短期間で \(2\) 問見たのでなんか書く。

この記事では、以下のような記法を使う。

• \(x_i\)：非負整数 \(x\) の下から \(i\) 番目のビットの値。x>>i&1
• \(\mathrm{MSB}(x)\)：正の数 \(x\) に対し、\(x_i=1\) となるような最大の \(i\)。

問題 \(1\)

ABC138 F - Coincidence

\(L,R\) が与えられるので、\((x,y)\) を数えて \(\bmod 10^9+7\) で出力せよ。

条件

• \(y\%x=y\oplus x\)
• \(L\le x\le y\le R\)

制約

• \(1\le L\le R\le10^{18}\)

条件を言い換えると、「\(\mathrm{MSB}(x)=\mathrm{MSB}(y)\) かつ、各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,1)\}\) を満たす」となる。
これにより、\(x\le y\) は必ず満たされることになるので、\(L\le x\) と \(y\le R\) についてだけ考えればよいということになる。

問題 \(2\)

Codeforces Round #597 (Div. 2) F. Daniel and Spring Cleaning

\(L,R\) が \(100\) 個以下与えられるので、それぞれについて \((x,y)\) を数えて出力せよ。

条件

• \(x+y=x\oplus y\)
• \(L\le x\le R\)
• \(L\le y\le R\)
• （\(x\le y\) でなくてもよい）

制約

• \(0\le L\le R\le10^9\)

条件を言い換えると、「各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,0)\}\)」となる。よって、\(x=y\) かつ条件を満たすものは \((x,y)=(0,0)\) だけであるので、さらに言い換えができ、
「『\(x\lt2^{\mathrm{MSB}(y)}\)（このとき、必ず \(x_{\mathrm{MSB}(y)}=0\) となる）かつ、各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,0)\}\)を満たすもの』\(\times2\)（\(L=0\) なら、さらに \(+1\)）」となる。
これにより、\(L\le x\) と \(y\le R\) についてだけ考えればよいということになる。

解法

「上位ビットから順に見て、\(i\) ビット目まで見た段階で、既に \(y\) の MSB が確定し、それ以降のビットを正しく埋めれば \(L\le x\le y\le R\) を満たすことができる、\((x_{\cdots,i+2,i+1,i},y_{\cdots,i+2,i+1,i})\) の個数」について DP をするために、次の \(4\) つの変数を用意する。
これらは、\(a,b,c,d\) から \(a',b',c',d'\) を計算し、\(a,b,c,d\) に \(a',b',c',d'\) を代入するようにして使う。

• \(a\)：\(L\le x\le y\le R\)
• \(b\)：\(L\le x\le y\lt R\)
• \(c\)：\(L\lt x\le y\le R\)
• \(d\)：\(L\lt x\le y\lt R\)

例えば \(c\) は、\(x\) が \(L\) を上回ることが確定しているが、\(y\) が \(R\) を下回ることが確定していないものについて数えるための変数である。
\(R_i=1\) のときに \(y_i=0\) にすれば、\(y\) が \(R\) を下回ることが確定するので、以降は \(d\) として数えることになる。

等号が外れるかどうかで分岐したいので、\(a\) からの遷移では \(L_i\) と \(R_i\) に注目し、\(b\) からの遷移では \(L_i\) に注目し、\(c\) からの遷移では \(R_i\) に注目する。

問題 \(1\) では、\(\left\lfloor\dfrac L{2^i}\right\rfloor\le1=1\le\left\lfloor\dfrac R{2^i}\right\rfloor\) のときに MSB として \((x_i,y_i)=(1,1)\) にすることができ、\(\le\) の等号が成立するかどうかで \(a,b,c,d\) のどれに該当するかを判定する。

問題 \(2\) では、\(\left\lfloor\dfrac L{2^i}\right\rfloor=0\lt1\le\left\lfloor\dfrac R{2^i}\right\rfloor\) のときに \(y\) のMSB として \((x_i,y_i)=(0,1)\) にすることができ、\(\le\) の等号が成立するかどうかで \(a,b\) のどちらに該当するかを判定する。

\(4\) つの変数を使うよりも、\(2\) つの bool 値を添え字とする配列を使ったほうがいい気がしているが、それについてはまだやってないので分からない。