Power or XOR?

题意翻译

$\land$ 这个符号的含义比较模糊，因为它既可以表示乘方运算 $a\land b=a^b$，又可以表示按位异或运算 $a\land b=a\oplus b$。 你有一个模糊不清的运算式 $E=A_1\land A_2\land\cdots\land A_n$。你需要将每个 $\land$ 替换为乘方运算或按位异或运算，以得到一个清晰的运算式 $E'$。 我们按下列方式计算 $E'$ 的值： - 乘方运算的优先级高于按位异或运算，即所有乘方运算都在按位异或运算之前计算。 - 连续的乘方运算和按位异或运算都是**从左往右算的**。 给定长度为 $n$ 的序列 $B$ 以及整数 $k$，设 $A_i=2^{B_i}$。 你需要求出所有至少有 $k$ 个 $\land$ 被替换为按位异或运算的运算式 $E'$ 的值的按位异或和。 因为答案可能非常大，你只需要输出答案二进制下的最后 $2^{20}$ 位去除所有前导零后的结果，即二进制下的答案 $\bmod 2^{2^{20}}$ 的结果。 特别的如果答案本身就是 $0$，就输出 $0$。 $1\leq n\leq2^{20};0\leq k<n;1\leq B_i<2^{20};$

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#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 $ .

输入输出格式

输入格式

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 $ .

输入输出样例

输入样例 #1

3 2
3 1 2

输出样例 #1

1110

输入样例 #2

3 1
3 1 2

输出样例 #2

1010010

输入样例 #3

3 0
3 1 2

输出样例 #3

1000000000000000001010010

输入样例 #4

2 1
1 1

输出样例 #4

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' $ : - $ 8\oplus 2\oplus 4 = 14 $ - $ 8^2\oplus 4 = 64\oplus 4= 68 $ - $ 8\oplus 2^4 = 8\oplus 16= 24 $ XOR of the values of all of these is $ 14\oplus 68\oplus 24 = 82 = (1010010)_2 $ .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 $ XOR of the values of all of these is $ 14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2 $ .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 $ .