Bounded XOR Count

Difficulty: 2200 5000 ms 128 MB

bitwise digit-dp

Count the integers i in [0, N] such that i XOR X is at most Y.

Input: one line with three integers N, X, Y.

Output: the count of qualifying i.

Constraints:

• 0 ≤ N, X, Y ≤ 10¹²

Sample Tests

5 3 4

4

0 0 0

1

Read the Editorial