Codeforces Round 785 (Div. 2) |
---|
Finished |
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:
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$$$.
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})$$$.
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$$$.
3 2 3 1 2
1110
3 1 3 1 2
1010010
3 0 3 1 2
1000000000000000001010010
2 1 1 1
0
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'$$$:
For the third testcase, there are four possible valid unambiguous expressions $$$E'$$$:
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$$$.
Name |
---|