### PROBLEM LINK:

**Author:** Prateek Gupta

**Tester:** Kevin Atienza

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Medium

### PREREQUISITES:

Dynamic programming, enumeration

### PROBLEM:

The **amazingness** of a number is defined using pseudocode. Given L and R, find the sum of the amazingnesses of all integers from L to R, inclusive.

### QUICK EXPLANATION:

Let \operatorname{ans}(L,R) be the answer. Note that \operatorname{ans}(L,R) = \operatorname{ans}(0,R) - \operatorname{ans}(0,L-1), so we can focus on the case L = 0.

Let \operatorname{digitXOR}(n) be the XOR of all digits of n. Thus, there are at most 16 distinct $\operatorname{digitXOR}(n)$s.

Let f(n) be the set of all $\operatorname{digitXOR}$s of all of n's **suffixes**. There are at most 2^{16} distinct $f(n)$s, and this can be represented as a **bitmask** of 16 bits.

The amazingness of n is uniquely determined by f(n). Thus, for every distinct possible f(n), we count the number of integers n \in [0,R] with this f(n). These counts can be simultaneously computed recursively.

### EXPLANATION:

Let \operatorname{ans}(L,R) be the sum of all amazingnesses of all integers from L to R. Notice that

so after rearranging, we have

This reduces a call to \operatorname{ans}(L,R) with *two* calls to \operatorname{ans}(L,R) with L = 0, which is potentially simpler. In fact, let’s define F(N) = \operatorname{ans}(0,N), so that \operatorname{ans}(L,R) = F(R) - F(L-1), and from now on, we will focus on computing F(N).

Before going further, we note that the first subtask can be solved without analyzing the “amazingness” function at all. We can just implement the given pseudocode, compute all amazingnesses from 0 to 10^6, and then compute cumulative sums. This way, we can get any F(N) we want with just a single lookup!

Unfortunately, this doesn’t pass the second subtask because N can now be up to 10^9. This time, we *might* need to analyze the “amazingness” function.

# Amazingness

Let’s analyze the `amazingness(a)`

function. Looking at the two loops in the code, we see that the variables `i`

and `j`

are looping in such a way that they **enumerate all substrings of a**.

Now, what does `val`

do? Looking at how it’s calculated, we see that each subsequent digit gets **XOR**-ed to `val`

as we loop `j`

. In fact, if you look carefully, at any time inside the inner loop `val`

is equal to `x[i] ^ x[i+1] ^ ... ^ x[j]`

, where `^`

is the XOR operator! In other words, `val`

loops through all XORs of all substrings of digits of `a`

, and the following snippet of code will be run for each such `val`

:

```
if (val not present in set s before) {
ans += val;
add val to set s
}
```

So let’s analyze this `if`

statement. This basically adds `val`

to a cumulative sum called `ans`

, *but only if* `val`

is not found in the set `s`

yet. If it’s found in `s`

, then it’s ignored. Otherwise, it’s added to `ans`

*and then* added to the set `s`

also. In other words, after looping through all `val`

s, ** ans becomes the sum of all distinct values of val.** Since

`ans`

is the return value, we now have a better understanding of what `amazingness(a)`

is:**The amazingness of a is the sum of all distinct XORs of substrings of digits of a.**

# Computing F(N)

Let’s now try to compute F(N). Recall that it’s defined as the sum of the amazingnesses of all integers \le N. But we can use our understanding of `amazingness`

above to help us do this efficiently.

First, note that every decimal digit has at most four bits. This means that `val`

, being the XOR of digits, can only have at most four bits too! Thus, we discover that `0 <= val < 16`

.

Next, notice that the amazingness of a is *uniquely determined* by the **set of all XORs of substrings of digits of a.** Let’s call this set a's **XOR-set**, and denote it as X(a). But since each XOR is < 16, every XOR-set must be a subset of \{0, 1, 2, \ldots, 15\}, which means there are only 2^{16} distinct XOR-sets. And if we can count how many a s correspond to each XOR-set that are \le N, we can compute F(N) easily.

To understand better, see the following pseudocode. Note that S is the XOR-set, and is represented as a **bitmask** of 16 bits, which is just an integer from 0 to 2^{16} - 1.

```
def F(N):
result = 0
for S = 0..2^16-1:
Let C = number of a's such that a <= N and X(a) = S
// compute amazingness
amazing = 0
for val = 0..15:
if (S & (1<<val)) != 0:
amazing += val
// update result
result += C * amazing
return result
```

If we have the `C`

values already, this runs in a fixed amount of operations, so this passes the time limit as long as we can compute each required `C`

efficiently. So we will describe that in the following sections.

## Computing `C`

s

For each XOR-set S \subset \{0, 1, 2, \ldots, 15\}, we want to count the number of a s such that a \le N and X(a) = S. Let’s denote this count by C[S]. Here, we’ll try to count all C[S] for all possible XOR-sets *simultaneously*, not one at a time.

Let’s try computing the C values with a **dynamic programming** procedure, adding one digit at the time from left to right. To do this, we must be able to “update” the XOR-set of a number when we append a digit to the right, and we also need to ensure that the numbers we’re constructing doesn’t exceed N.

There’s a problem with this, though. By appending a digit, there isn’t enough information to obtain the new XOR-set. Indeed, appending the same digit to two numbers with the same XOR-set may even result in different XOR-sets! Consider for example appending the digit 4 to the numbers 21 and 12. 21 have 12 have the same XOR-set: X(21) = X(12) = \{0, 1, 2, 3\}. However, X(214) = \{0, 1, 2, 3, 4, 5, 7\} \not= X(124) = \{0, 1, 2, 3, 4, 6, 7\}. Clearly, we need to encode more information other than the XOR-set of a number.

The insight is to also store the set of all XORs of **suffixes** of digits of a. Let’s call this set a's **suffix-XOR-set**, and denote this by Y(a). By having both X(a) and Y(a), the updated XOR-set is now uniquely determined when we append a digit to a.

Specifically, let a' be the integer when the digit d is appended to the right of a, i.e., a' = 10a + d. Then:

where \oplus stands for the bitwise XOR operation.

Unfortunately, the number of distinct (X(a), Y(a)) pairs may be very large. To see why, notice that Y(a) is also a subset of \{0, 1, 2, \ldots, 15\} like X(a). Hence, on the surface there seems to be 2^{16}\cdot 2^{16} = 4^{16} \approx 4.3\cdot 10^9 pairs possible, which is too high. Fortunately, we can reduce this count by noticing that Y(a) is always a subset of X(a). Hence, there are only 3^{16}\approx 4.3\cdot 10^7 pairs, which is more manageable. (To see why 3^{16}, notice that for every \text{val} \in \{0, 1, 2, \ldots, 15\}, there are only three possibilities: (1) \text{val} is in X(a) and Y(a), (2) \text{val} is in X(a) but not in Y(a), and (3) \text{val} is neither in X(a) nor in Y(a).)

A second complication is ensuring that the numbers we are constructing are all \le N. But this is simpler to remedy. Since we are adding digits from left to right, the only time that we can append a digit *and then* exceed N is when all previously-added digits are equal to their corresponding digits in N! This means we simply have to separate the (X(a), Y(a)) pair of the number a whose digits are equal to the first few digits of N. For everything else, adding a digit will not exceed N.

With that in mind, we can now implement our enumeration algorithm, using pseudocode.

```
def append((X, Y), d):
new_Y = union({0}, {s ^ d for all s in Y})
new_X = union(X, new_Y)
return (new_X, new_Y)
def compute_Cs(N):
(C, XY_last) = _compute_Cs(N)
C[XY_last] += 1
return C
def _compute_Cs(N):
if N == 0:
C = (empty map/dictionary)
XY_last = ({0}, {0})
return (C, XY_last)
else:
prev_C, prev_XY_last = _compute_Cs(N/10)
// compute new 'C'
C = (empty map/dictionary)
for (X, Y) in prev_C.keys():
for d = 0..9:
(new_X, new_Y) = append((X, Y), d)
C[(new_X, new_Y)] += prev_C[(X, Y)]
// try appending small digits to prev_XY_last
last_d = N%10 // last digit of N
for d = 0..last_d-1:
(new_X, new_Y) = append(prev_XY_last, d)
C[(new_X, new_Y)] += 1
// compute new 'XY_last' by appending last_d to prev_XY_last
XY_last = append(prev_XY_last, last_d)
// return the new (C, XY_last)
return (C, XY_last)
```

Note that `{}`

denotes sets, so for example `{0}`

denotes the set containing only the integer 0. These sets are subsets of \{0, 1, 2, \ldots, 15\}, so they can be implemented as bitmasks.

Once we have `compute_Cs`

, we can now compute `F(N)`

straightforwardly.

```
def F(N):
C = compute_Cs(N)
result = 0
for (X, Y) in C.keys():
// compute amazingness
amazing = 0
for val = 0..15:
if X contains val:
amazing += val
// update result
result += C[(X, Y)] * amazing
return result
```

So what’s the running time? There are approximately \log_{10} N calls to `_compute_Cs`

, and each step requires 3^{16}\cdot 10 steps. Thus, this might take potentially 3^{16}\cdot 10\cdot \log_{10} N steps which is slow for large N. But actually the number of keys in `C`

is very far from 3^{16} in practice, so with the right implementation, this could pass the time limit!

## Computing `C`

s better

We can actually improve the previous algorithm by noticing that we don’t need to store the whole (X(a), Y(a)) pair, because you can compute X(a) just from Y(a)!

To see this, note that the XOR of any substring is just the XOR of two *suffixes*! For example, if you want to compute the XOR of the digits (N_i, N_{i+1}, \ldots, N_j), we just need to XOR the following suffixes: (N_i, N_{i+1}, \ldots) and (N_{j+1}, N_{j+2}, \ldots). This is true because XOR cancels itself, i.e. x\oplus y\oplus y = x.

This means that the above can be simplified into the following:

```
def append(Y, d):
new_Y = union({0}, {s ^ d for all s in Y})
return new_Y
def compute_Cs(N):
(C, Y_last) = _compute_Cs(N)
C[Y_last] += 1
return C
def _compute_Cs(N):
if N == 0:
C = (empty map/dictionary)
Y_last = {0}
return (C, Y_last)
else:
prev_C, prev_Y_last = _compute_Cs(N/10)
// compute new 'C'
C = (empty map/dictionary)
for Y in prev_C.keys():
for d = 0..9:
new_Y = append(Y, d)
C[new_Y] += prev_C[Y]
// try appending small digits to prev_Y_last
last_d = N%10 // last digit of N
for d = 0..last_d-1:
new_Y = append(prev_Y_last, d)
C[new_Y] += 1
// compute new 'Y_last' by appending last_d to prev_Y_last
Y_last = append(prev_Y_last, last_d)
// return the new (C, Y_last)
return (C, Y_last)
def F(N):
C = compute_Cs(N)
result = 0
for Y in C.keys():
// compute X from Y
X = {} // empty set
for v = 0..15:
if Y contains v:
for w = 0..15:
if Y contains w:
X.add(v ^ w)
// compute amazingness
amazing = 0
for val = 0..15:
if X contains val:
amazing += val
// update result
result += C[Y] * amazing
return result
```

Computing `X`

from `Y`

can actually be precomputed so it takes O(1) time during the computation of F(N). Also, with this simplification, and with the fact that X and Y can be represented as a bitmask of 16 bits, we can now ditch the map/dictionary and just use a regular array!

To see an implementation in C++, see the tester’s solution. Note that in this solution, even the `append`

function has been precomputed, to further optimize.

### Time Complexity:

O(2^k d \log_d b) for k = 16 and d = 10