409571: GYM103634 B Xor or floor ?

After solving "Traveling salesman" problem in $$$O(E+V)$$$, multiplying polynomials in $$$O(N)$$$, proving the Collatz conjecture, understanding physics and finding a quadratic algorithm for multiplying matricies, $$$K0Kalaru47$$$ challanges you with this problem, in exchange for a chance of winning this $$$InfOleague™$$$ contest.

You are given an array $$$A$$$ of $$$N$$$ values smaller than $$$M$$$. The cost of a subset is the minimum $$$xor$$$ across all pairs in the subset. More formally, the cost of a set $$$B= {B_1,B_2,...,B_k}$$$ is equal to $$$min_{i \neq j \in [1,k]} (B_i \oplus B_j)$$$, where $$$\oplus$$$ denotes the bitwise xor operation. Find the sum of costs across all possible subsets of length greater than $$$1$$$ modulo $$$MOD$$$.

The input consists of integers $$$N,M,MOD$$$ followed by an array $$$A$$$ of length $$$N$$$ with values in range $$$[0,M]$$$.

Print one integer: The sum of costs across all subsets of length greater than $$$1$$$.

• For all test data , $$$N \cdot M \le 10^6$$$ , $$$2 \le MOD \le 10^9$$$
• For 30 points , $$$N,M \le 100$$$
• For the remaining $$$70$$$ points, there are no further restrictions
• Note that $$$MOD$$$ may not be a prime number !

3 5 666013
4 2 5

15

12 100 66013
32 69 39 51 49 30 51 32 0 0 0 100

16807

In the first sample , all the possible subsets are :

• $$$[1,2,3]$$$ with cost $$$min(a[1] \oplus a[3],a[2] \oplus a[3],a[1] \oplus a[3])$$$ = 1
• $$$[1,2]$$$ with cost $$$min(a[1] \oplus a[2]) = 6$$$
• $$$[2,3]$$$ with cost $$$min(a[1] \oplus a[3]) = 1$$$
• $$$[1,3]$$$ with cost $$$min(a[2] \oplus a[3]) = 7$$$

Therefore, the final answer is $$$1+6+1+7 = 15$$$