/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 L,R,V が与えられます． 次の条件を両方満たす整数の組 (l,r) の個数を 998244353 で割った余りを求めてください．
- L \leq l \leq r \leq R
- l \oplus (l+1) \oplus \cdots \oplus r=V
ただしここで，\oplus はビット単位 \mathrm{XOR} 演算を表します．
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \leq L \leq R \leq 10^{18}
- 0 \leq V \leq 10^{18}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
L R V
出力
答えを出力せよ．
入力例 1
1 3 3
出力例 1
2
条件を満たすのは，(l,r)=(1,2) と (l,r)=(3,3) の 2 つです．
入力例 2
10 20 0
出力例 2
6
入力例 3
1 1 1
出力例 3
1
入力例 4
12345 56789 34567
出力例 4
16950
Score : 700 points
Problem Statement
Given are integers L, R, and V. Find the number of pairs of integers (l,r) that satisfy both of the conditions below, modulo 998244353.
- L \leq l \leq r \leq R
- l \oplus (l+1) \oplus \cdots \oplus r=V
Here, \oplus denotes the bitwise \mathrm{XOR} operation.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 1 \leq L \leq R \leq 10^{18}
- 0 \leq V \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
L R V
Output
Print the answer.
Sample Input 1
1 3 3
Sample Output 1
2
The two pairs satisfying the conditions are (l,r)=(1,2) and (l,r)=(3,3).
Sample Input 2
10 20 0
Sample Output 2
6
Sample Input 3
1 1 1
Sample Output 3
1
Sample Input 4
12345 56789 34567
Sample Output 4
16950