Power or XOR?
Contest: Codeforces Round 785 (Div. 2)
Difficulty rating: 2500
Tags: bitmasks, combinatorics, math, number theory

The symbol $$$\wedge$$$ is quite ambiguous, especially when used without context. Sometimes it is used to denote a power ($$$a\wedge b = a^b$$$) and sometimes it is used to denote the XOR operation ($$$a\wedge b=a\oplus b$$$).

You have an ambiguous expression $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$. You can replace each $$$\wedge$$$ symbol with either a $$$\texttt{Power}$$$ operation or a $$$\texttt{XOR}$$$ operation to get an unambiguous expression $$$E'$$$.

The value of this expression $$$E'$$$ is determined according to the following rules:

- All $$$\texttt{Power}$$$ operations are performed before any $$$\texttt{XOR}$$$ operation. In other words, the $$$\texttt{Power}$$$ operation takes precedence over $$$\texttt{XOR}$$$ operation. For example, $$$4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$$$.
- Consecutive powers are calculated from left to right. For example, $$$2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$$$.

You are given an array $$$B$$$ of length $$$n$$$ and an integer $$$k$$$. The array $$$A$$$ is given by $$$A_i=2^{B_i}$$$ and the expression $$$E$$$ is given by $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$. You need to find the XOR of the values of all possible unambiguous expressions $$$E'$$$ which can be obtained from $$$E$$$ and has at least $$$k$$$ $$$\wedge$$$ symbols used as $$$\texttt{XOR}$$$ operation. Since the answer can be very large, you need to find it modulo $$$2^{2^{20}}$$$. Since this number can also be very large, you need to print its binary representation without leading zeroes. If the answer is equal to $$$0$$$, print $$$0$$$.

Input format:
The first line of input contains two integers $$$n$$$ and $$$k$$$ $$$(1\leq n\leq 2^{20}, 0\leq k < n)$$$.

The second line of input contains $$$n$$$ integers $$$B_1,B_2,\ldots,B_n$$$ $$$(1\leq B_i < 2^{20})$$$.

Output format:
Print a single line containing a binary string without leading zeroes denoting the answer to the problem. If the answer is equal to $$$0$$$, print $$$0$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
For each of the testcases $$$1$$$ to $$$3$$$, $$$A = \{2^3,2^1,2^2\} = \{8,2,4\}$$$ and $$$E=8\wedge 2\wedge 4$$$.

For the first testcase, there is only one possible valid unambiguous expression $$$E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$$$.

For the second testcase, there are three possible valid unambiguous expressions $$$E'$$$:

- $$$8\oplus 2\oplus 4 = 14$$$
- $$$8^2\oplus 4 = 64\oplus 4= 68$$$
- $$$8\oplus 2^4 = 8\oplus 16= 24$$$

For the third testcase, there are four possible valid unambiguous expressions $$$E'$$$:

- $$$8\oplus 2\oplus 4 = 14$$$
- $$$8^2\oplus 4 = 64\oplus 4= 68$$$
- $$$8\oplus 2^4 = 8\oplus 16= 24$$$
- $$$(8^2)^4 = 64^4 = 2^{24} = 16777216$$$

For the fourth testcase, $$$A=\{2,2\}$$$ and $$$E=2\wedge 2$$$. The only possible valid unambiguous expression $$$E' = 2\oplus 2 = 0 = (0)_2$$$.

Example input:
3 2
3 1 2

Example output:
1110

Example input:
3 1
3 1 2

Example output:
1010010

Editorial:
Let's consider a subsegment $$$[A_{l}\wedge A_{l+1}\wedge A_{l+2}\wedge\ldots\wedge A_r]$$$. Let all the $$$\wedge$$$ symbols in this segment be replaced by $$$\texttt{Power}$$$ and the $$$\wedge$$$ symbols before $$$A_l$$$ and after $$$A_r$$$ be replaced by $$$\texttt{XOR}$$$. Then the value of this segment will not be affected by the rest of the expression. Moreover, out of all the expressions in which this segment appears as above, it will contribute the same value to the final answer. Since the final answer is also a $$$\texttt{XOR}$$$, if the segment $$$[l\ldots r]$$$ appears in the above mentioned form in odd number of valid unambiguous expressions, it will contribute $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ to the final answer else it will contribute nothing. We can find the contribution of each segment $$$[l\ldots r]$$$ independently for all values of $$$1\leq l < r \leq n$$$.
Now, there are two things we need to find out:
1. How much $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will contribute to the final answer, modulo $$$MOD = 2^{1048576}$$$.
2. What is the parity of the count of valid unambiguous expressions, in which the segment $$$[l...r]$$$ appears as $$$... \oplus (\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r} \oplus \ldots$$$.
1. Notice that since all the elements of $$$A$$$ are powers of $$$2$$$, $$$S(l,r)=(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will also be a power of $$$2$$$. It means that $$$\texttt{XOR}$$$-ing it with answer will flip not more than $$$1$$$ bit in the answer. The rest of the calculations is pretty straightforward. $$$S(l,r) = 2^{B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}}$$$ by properties of exponents. So, if it contributes to the answer, it will flip the $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}-$$$th bit of the answer. Now, note that if $$$S\geq 2^{1048576}$$$, it will have no effect on the answer because $$$S(l,r) \bmod 2^{1048576}$$$ will then be $$$0$$$. So, we care only for those $$$(l,r)$$$ for which $$$S(l,r) < 2^{1048576}$$$. Since $$$B_i\geq 1$$$, $$$A_i\geq 2$$$ and so, $$$r-l \leq 20$$$ because $$$2^{20} = 1048576$$$. Thus, it is sufficient to calculate $$$S(l,r)$$$ for only $$$20$$$ values of $$$r$$$ per value of $$$l$$$.
2. We have used $$$r-l$$$ $$$\wedge$$$ operators as $$$\texttt{Power}$$$ and $$$0$$$, $$$1$$$ or $$$2$$$ $$$\wedge$$$ operators as $$$\texttt{XOR}$$$. Let's say that out of the $$$m$$$ unused operators, we need to use at least $$$q$$$ of them as $$$\texttt{XOR}$$$. Then the number of ways to do this is $$$\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}$$$. Infact, instead of finding this value, we are only interested in finding whether it is even or odd. So, we need the value of
$$$\big[\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}\big]\bmod 2=$$$ $$$\big[\big\{\binom{m-1}{q}+\binom{m-1}{q-1}\big\} + \big\{\binom{m-1}{q+1}+\binom{m-1}{q}\big\} + \big\{\binom{m-1}{q+2}+\binom{m-1}{q+1}\big\} + \ldots + \big\{\binom{m-1}{m-1}+\binom{m-1}{m-2}\big\} + \binom{m}{m}\big] \bmod 2=$$$ $$$\big[\binom{m-1}{q-1} + \binom{m-1}{m-1} + \binom{m}{m}]\bmod 2 = \binom{m-1}{q-1} \bmod 2$$$
as $$$(a + a) \bmod 2 = 0$$$ and $$$\binom{x}{x} = 1$$$ by definition. $$$\binom{m-1}{q-1} \bmod 2$$$ can be found using Lucas' Theorem. It turns out that $$$\binom{n}{r}$$$ is odd if and only if $$$r$$$ is a submask of $$$n$$$, i.e., $$$n\&r=r$$$. Note that there are also many other ways to find this value (like Submasks DP or using the fact that $$$r-l\leq 20$$$ for precomputation) but this is the easiest one.
Some final notes -
1. We can maintain the final answer as a binary string of length $$$1048576$$$. Find the value $$$X = B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ and if the required parity is odd and $$$X < 1048576$$$, flip the $$$X-$$$th bit of the string.
2. We need to be careful while calculating $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ since $$$A_i$$$ can be as large as $$$2^{1048575}$$$. But since we are interested in values that evaluate to something smaller than $$$1048576$$$, we will never try to multiply $$$A_i$$$ for anything with $$$B_i > 20$$$.
3. Calculating the parity of $$$\binom{n}{r}$$$ in $$$\mathcal{O}(\log n)$$$ may time out. The constraints are strict enough.
Total time Complexity - $$$\mathcal{O}(n \log \log MOD)$$$
Bonus task: Try to solve the problem if $$$B_i\geq 0$$$ and if powers are calculated from right to left.