CF1673E Power or XOR?

符号 $ \wedge $ 非常容易引起歧义，尤其是在没有上下文的情况下。有时它用来表示幂运算（$ a\wedge b = a^b $），有时用来表示 [异或](https://en.wikipedia.org/wiki/Bitwise_operation#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' $ 的值的异或和，其中至少有 $ 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 $ 个测试用例，$ 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 $ 这些值的异或和为 $ 14\oplus 68\oplus 24 = 82 = (1010010)_2 $。 对于第三个测试用例，有四种可能的无歧义表达式 $ 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 $ 这些值的异或和为 $ 14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2 $。 对于第四个测试用例，$ A=\{2,2\} $，$ E=2\wedge 2 $。唯一可能的无歧义表达式 $ E' = 2\oplus 2 = 0 = (0)_2 $。 由 ChatGPT 4.1 翻译