My $$$\mathcal O(n2^n)$$$ solution passed easily.

One of my classmate wrote a O(n*(2^n)) code and got TLE. Actually I think the contest meant to ban some codes with to much constant.

It is related to your constant. Since I'm using C# I have to handle the constant very carefully. My submission.

Bad (appl)E!!!

(some music starts)

Then this problem will only worth 350 points.

Whether $$$M$$$ is a prime number or not doesn’t really matter much.

But $$$\sum C_i$$$ is only 5000.

And I think maybe E is too easy.

$$$\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$$$

You can use it to avoid division.

let me guess 🤔 it was that evil 51th test case.

My solution:

Consider solving for a fixed $$$x$$$ first.

We can build a trie of $$$A$$$ then traverse it to find the $$$A_j$$$ that minimize $$$x \oplus A_j$$$. Which can be found it the following manner:

Start from the root, and assume the current bit we are consider is $$$i$$$-th bit.

• if there is a child correspond to the $$$i$$$-th bit of $$$x$$$, go to that child
• otherwise, go to the only child, which will incur $$$2^i$$$ cost because $$$i$$$-th bit of $$$x \oplus A_j$$$ must be $$$1$$$.

Then to deal with all $$$x \in [0, M)$$$, notice that all $$$x$$$'s go to a child would still be consecutive under $$$\pmod {2^i}$$$, so to maintain all $$$x$$$'s go to a child, we store (first term of the consecutive $$$x$$$'s, the number of $$$x$$$'s) then everything can be dealt easily. (ex. $$$(2, 7)$$$ under $$$\pmod {2^2}$$$ represent $$$[2, 3, 0, 1, 2, 3, 0]$$$)

More specifically, we start from root with $$$(0, M)$$$ and traverse the trie with a BFS. Assume we have $$$(s, len)$$$ currently.

• if there is two children, split all integers in $$$(s, len)$$$ into two group by their $$$i$$$-th bit, then send two group to their respective children.
• otherwise send all integers to the only children, if the only child represent $$$1$$$, this would incur a cost of $$$2^i \cdot (\text{the number of integers in (s, len) with i-th bit being 0})$$$, and vise versa.

My solution of this G is a simple divide and conquer algorithm.
In the below,we extend every a to 30 digits.
Consider this greedy algorithm:There is a fixed x,you want to find the minimum value of $$$x\oplus a[i](l\le i\le r)$$$ which is guaranteed that the first t-1 digits of $$$a[i](l\le i\le r)$$$ are the same
Let the answer be $$$x\oplus a[i_0]$$$
if the t-th digit is same among $$$a[i](l\le i\le r)$$$:add 1 from t
otherwise:$$$a[i_0]$$$ must have the same t-th digit with x
Sort a in increasing order,let $$$f(m,l,r,t)=\sum\limits_{x=0}^{m-1}\min\limits_{l\le i\le r}((x\oplus a_i)\bmod 2^t)$$$.The transition is easy.

my code