← 返回题目列表

Codeforces · 1673/E

E. 电源还是异或?

中文机器翻译题面 查看原题

符号 $$$\wedge$$$ 非常不明确,特别是在没有上下文的情况下使用时。有时它用于表示幂 ($$$a\wedge b = a^b$$$),有时用于表示 XOR 运算 ($$$a\wedge b=a\oplus b$$$)。

您的表达式不明确 $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$。您可以将每个 $$$\wedge$$$ 符号替换为 $$$\texttt{Power}$$$ 运算或 $$$\texttt{XOR}$$$ 运算,以获得明确的表达式 $$$E'$$$。

该表达式 $$$E'$$$ 的值根据以下规则确定:

- 所有 $$$\texttt{Power}$$$ 操作均在任何 $$$\texttt{XOR}$$$ 操作之前执行。换句话说,$$$\texttt{Power}$$$ 运算优先于 $$$\texttt{XOR}$$$ 运算。例如,$$$4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$$$。
- 连续幂从左到右计算。例如,$$$2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$$$。

给定一个长度为 $$$n$$$ 的数组 $$$B$$$ 和一个整数 $$$k$$$。数组 $$$A$$$ 由 $$$A_i=2^{B_i}$$$ 给出,表达式 $$$E$$$ 由 $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$ 给出。您需要找到所有可能的明确表达式 $$$E'$$$ 的值的异或,这些表达式可以从 $$$E$$$ 获得,并且至少有 $$$k$$$ $$$\wedge$$$ 符号用作 $$$\texttt{XOR}$$$ 运算。由于答案可能非常大,因此您需要对 $$$2^{2^{20}}$$$ 求模。由于该数字也可能非常大,因此您需要打印其二进制表示形式,不带前导零。如果答案等于$$$0$$$,则打印$$$0$$$。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1\leq n\leq 2^{20}, 0\leq k < n)$$$。

输入的第二行包含 $$$n$$$ 整数 $$$B_1,B_2,\ldots,B_n$$$ $$$(1\leq B_i < 2^{20})$$$。

输出

打印包含二进制字符串的单行,不带前导零来表示问题的答案。如果答案等于$$$0$$$,则打印$$$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

注意

对于每个测试用例 $$$1$$$ 到 $$$3$$$,$$$A = \{2^3,2^1,2^2\} = \{8,2,4\}$$$ 和 $$$E=8\wedge 2\wedge 4$$$。

对于第一个测试用例,只有一个可能的有效明确表达式 $$$E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$$$。

对于第二个测试用例,存在三个可能的有效明确表达式 $$$E'$$$:

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

对于第三个测试用例,有四个可能的有效明确表达式 $$$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$$$

对于第四个测试用例,$$$A=\{2,2\}$$$ 和 $$$E=2\wedge 2$$$。唯一可能的有效明确表达式 $$$E' = 2\oplus 2 = 0 = (0)_2$$$。