ABC138 F. Coincidence

問題

整数L,Rが与えられる。
整数の組(x,y)がL<=x

制約

• 1 <= L <= R <= 10^18

解法

(解説放送より)

a xor bは各ビットの繰り上がりのない足し算と考えられる。
y%xは0からx-1までの整数であり、y xor xはx<=yであるので、yの方が一番高いビットがxの一番高いビットよりも上回ってしまうとy xor xがxよりも大きくなってしまって条件を満たせない。
したがって、yはxと一番高いビットが同じところまでのものになる。
また、このとき、y/x=1を満たすので、y%x = y-xと書くことができる。

y xor xの方は、a xor bが「a+b-2*(a&b)」と書けることから、

y-x = y+x-2*(y&x)
<=> 2x = 2*(y&x)
<=> x = y&x

を満たすx,yの組を探す問題と言い換えられる。

xとyのANDがxと一致するというのは、xとyの各ビットが(0,0), (0,1), (1,1)の場合のものなので、これを桁DPで求める。
条件として、「L<=x」「y<=R」「最も高いビットが同じ」もあるため、それぞれ境界ギリギリか？とすでに(1,1)で使ったか？をフラグに持たせると、

dp[i][j][k][l] := i桁目で、j=xはLギリギリか？、k=yはRギリギリか？、l=すでに1番高いビットが(x,y)=(1,1)で出てきているか？を満たす個数

のように書ける。

遷移は、複雑になるので、(x,y)について、(0,0), (0,1), (1,1)が入ってくるとして、ダメパターンと次の遷移パターンを列挙する

• l=0(まだ1番高いビットがでてきていない)のときで、(0,1)だったらダメ
• j=0(xがLギリギリ)のときで、Lのiビット目が1なのにxが0なら下回るのでダメ
• k=0(yがRギリギリ)のときで、Rのiビット目が0なのにyが1なら上回るのでダメ
• (1,1)なら一番高いビットが出てくることになるのでl=1に遷移
• Lのiビット目が0でxが1ならL
• Rのiビット目が1でyが0ならy

のように書けばよい。

最終的な答えは、iが大きい方から計算して、i=0のときのj,k,lの全パターンをあわせたものを出力すれば良い。