[ABC138F] Coincidence

ID: 18051

传统题

2000ms

1024MiB

难度: 6

上传者:

标签>

数位 dp

配点 : $600$ 点

問題文

整数 $L, R$ が与えられます。整数の組 $(x, y)$ $(L \leq x \leq y \leq R)$ であって、 $y$ を $x$ で割った余りが $y \text{ XOR } x$ に等しいものの個数を $10^9 + 7$ で割ったあまりを求めてください。

$\text{ XOR }$ とは

整数 $A, B$ のビットごとの排他的論理和 $a \text{ XOR } b$ は、以下のように定義されます。

$a \text{ XOR } b$ を二進数表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $A, B$ を二進数表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、 $3 \text{ XOR } 5 = 6$ となります (二進数表記すると: $011 \text{ XOR } 101 = 110$ )。

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

$L$ $R$

条件を満たす整数の組 $(x, y)$ $(L \leq x \leq y \leq R)$ の個数を $10^9 + 7$ で割ったあまりを出力せよ。

2 3

条件を満たす組は $(2, 2), (2, 3), (3, 3)$ の $3$ 通りです。

10 100

1 1000000000000000000

68038601

個数を $10^9 + 7$ で割ったあまりを計算することを忘れないでください。