PROBLEM LINK:
Contest
Practice
Author:Utkarsh Saxena
Testers:GVS Akhil, Kumar Abhinav
Editorialist:Kumar Abhinav
DIFFICULTY:
Hard
PREREQUISITES:
Math, Combinatorics, Generator Functions
PROBLEM:
Maximise A_0 XOR A_1 XOR A_2 … XOR A_{N-1}, where A_i \in (1,2,4,...,2^{k-1}), and find no of different ways to do it modulo 10^9+7
EXPLANATION:
We’ll split the solution into two parts:-
Part 1: $N-K$ is even
All the numbers in $S$ must occur odd number of times Number of ordered solutions of this is $\sum \frac{N!}{x_1!x_2!...x_k!}$ over all $x_1+x_2+...+x_k=N$ where $x_i$ is odd. This is equivalent to the coefficient of $x^N$ in $\left ( \frac{x}{1!} + \frac{x^3}{3!} + \frac{x^5}{5!} + ...\right )^k$ The generator function of the above polynomial is $\left ( \frac{e^x - e^{-x}}{2} \right )^k$ Thus the solution is the coefficient of $x^N$ of the above eqn, which on expanding binomially we get $\sum_{r=0}^{k} \frac{\left (-1 \right )^r \binom{k}{r}e^{(k-2r)x}}{2^k}$ Coefficient of $x^N$ in $e^bx = \frac{b^N}{N!}$, thus coefficient of $x^N$ in the above eqn will be, multiplied by $N!$, is $\sum_{r=0}^{k} \frac{\left (-1 \right )^r \binom{k}{r}(k-2r)^{n}}{2^k}$ which is the final answer to Part 1.Part 2: $N-K$ is odd
Coefficient of $1$ is to be kept even, while rest of the coefficients are odd Polynomial for even $x$ is $\frac{x^0}{0!}+\frac{x^2}{2!}+\frac{x^4}{4!}+...$ Whose generator is $\left ( \frac{e^x + e^{-x}}{2} \right )$Thus the final expression, with 1 even generator and k-1 odd generators are
\left ( \frac{e^x + e^{-x}}{2} \right )\left ( \frac{e^x - e^{-x}}{2} \right )^{k-1}
Which leads us to the final solution is, after reducing similarly as above:-
\sum_{r=0}^{k-1} \frac{\left (-1 \right )^r \binom{k-1}{r}((k-2r)^{n}+(k-2r-2)^{n})}{2^k}
TIME COMPLEXITY:
O(Klogn) per testcase + preprocessing to compute \binom{k}{r}