CNTL - Editorial

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}

SOLUTIONS:

18049750
18049760

1 Like