Varying Kibibits
Contest: VK Cup 2017 - Round 2
Difficulty rating: 2700
Tags: bitmasks, dp

You are given n integers a1, a2, ..., an. Denote this list of integers as T.

Let f(L) be a function that takes in a non-empty list of integers L.

The function will output another integer as follows:

- First, all integers in L are padded with leading zeros so they are all the same length as the maximum length number in L.
- We will construct a string where the i-th character is the minimum of the i-th character in padded input numbers.
- The output is the number representing the string interpreted in base 10.

For example f(10, 9) = 0, f(123, 321) = 121, f(530, 932, 81) = 30.

Define the function

$$$$

In other words, G(x) is the sum of squares of sum of elements of nonempty subsequences of T that evaluate to x when plugged into f modulo 1 000 000 007, then multiplied by x. The last multiplication is not modded.

You would like to compute G(0), G(1), ..., G(999 999). To reduce the output size, print the value $$G(0) \oplus G(1) \oplus G(2) \oplus \ldots \oplus G(999\ 999)$$, where $$\bigcirc$$ denotes the bitwise XOR operator.

Input format:
The first line contains the integer n (1 ≤ n ≤ 1 000 000) — the size of list T.

The next line contains n space-separated integers, a1, a2, ..., an (0 ≤ ai ≤ 999 999) — the elements of the list.

Output format:
Output a single integer, the answer to the problem.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first sample, the nonzero values of G are G(121) = 144 611 577, G(123) = 58 401 999, G(321) = 279 403 857, G(555) = 170 953 875. The bitwise XOR of these numbers is equal to 292 711 924.

For example, $$G(123) = 123 \cdot \left( ( ( 1 2 3 ) ^ { 2 } + ( 1 2 3 + 5 5 5 ) ^ { 2 } ) \right) \bmod 100000007 = 58401999$$, since the subsequences [123] and [123, 555] evaluate to 123 when plugged into f.

For the second sample, we have $$G(999\ 999) = 999\ 999 \cdot (999\ 999^2 \bmod 1\ 000\ 000\ 007)$$

For the last sample, we have $$G(1) = \sum_{i=1}^{10} {10 \choose i} i^2 = 28160$$, where $${ \binom { 10 } { i } }$$ is the binomial coefficient.

Example input:
3
123 321 555

Example output:
292711924

Example input:
1
999999

Example output:
997992010006992

Editorial:
There are two approaches. One is inclusion exclusion. The other is a modification of the fast walsh hadamard transform.
Inclusion Exclusion: Let's change definition of G(x) so that f(S) >= x rather than f(S) = x. Here "y >= x" means that if y and x are considered as strings, then each digit in a particular position in y is greater than its corresponding digit in x. This is then easy to compute, since the numbers we can use must satisfy the constraint that each digit is larger than the corresponding position in x. So, we can go from 999, 999 to 0 and do inclusion/exclusion to change the >= condition to =, by fixing which digits are fixed and which ones are strictly greater, so it takes 26 time per value of x to compute.
Fast Walsh Hadamard transform: Let's consider the simplified problem where we just want to know the number of subsets that evaluate to x for all values of x.
Let f(freq) taken in a frequency array of length 10^k, and returns a list of length 10^k, where the i-th element represents the result. When k = 0, this is easy to compute, it is just 2freq[0].
Let's fix the value of the topmost digit. We can split our frequency array into 10 parts, representing which one is the top digt. Let's label these freq_0, freq_1, ..., freq_9 (these have length 10^(k-1)).
Then, we can compute g_9 = f(freq_9) g_8 = f(freq_9+freq_8) g_7 = f(freq_9+freq_8+freq_7) ... g_0 = f(freq_9+freq_8+...+freq_0) (The plus signs here are element by element addition, so [0,3] + [5,4] = [5,7] for example).
Then, we can combine these to get the answer to our original problem. Namely, our final answer will be (g_0 - g_1), (g_1 - g_2), ... , g_9 (i.e. concatenate the element by element subtraction of g_1 from g_0 to g_1-g_2 and so on).
Of course, we don't need to do this recursively, we can do it in a loop (see my java code for example).
Back to the original problem, we need to keep track of three values when doing the first pass of our algorithm, the number of elements, sum of elements, and sum of squares of elements. Then, in our base case, we can use these three numbers to compute the desired sum.
The runtime of this is T(n) = 10 * T(n/10) + O(n) = O(n log_10(n)).