309402: CF1673E. Power or XOR?
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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