Power or XOR? Solution | Codeforces Problem Solution 2022

Power or XOR? Solution | Codeforces Problem Solution 2022

E. Power or XOR?

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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 𝐸=𝐴1∧𝐴2∧𝐴3∧…∧𝐴𝑛$E=A_1\wedge A_2\wedge A_3\wedge \dots \wedge A_n$. You can replace each ∧$\wedge$ symbol with either a 𝙿𝚘𝚠𝚎𝚛$\mathtt{\text{Power}}$ operation or a 𝚇𝙾𝚁$\mathtt{\text{XOR}}$ operation to get an unambiguous expression 𝐸′$E^{\prime }$.

The value of this expression 𝐸′$E^{\prime }$ is determined according to the following rules:

• All 𝙿𝚘𝚠𝚎𝚛$\mathtt{\text{Power}}$ operations are performed before any 𝚇𝙾𝚁$\mathtt{\text{XOR}}$ operation. In other words, the 𝙿𝚘𝚠𝚎𝚛$\mathtt{\text{Power}}$ operation takes precedence over 𝚇𝙾𝚁$\mathtt{\text{XOR}}$ operation. For example, 4𝚇𝙾𝚁6𝙿𝚘𝚠𝚎𝚛2=4⊕(62)=4⊕36=32$4\mathtt{\text{XOR}}6\mathtt{\text{Power}}2=4\oplus (6^2)=4\oplus 36=32$.
• Consecutive powers are calculated from left to right. For example, 2𝙿𝚘𝚠𝚎𝚛3𝙿𝚘𝚠𝚎𝚛4=(23)4=84=4096$2\mathtt{\text{Power}}3\mathtt{\text{Power}}4=(2^3{)}^4=8^4=4096$.

Solution Click Below:- CLICK HERE

You are given an array 𝐵$B$ of length 𝑛$n$ and an integer 𝑘$k$. The array 𝐴$A$ is given by 𝐴𝑖=2𝐵𝑖$A_i=2^{B_i}$ and the expression 𝐸$E$ is given by 𝐸=𝐴1∧𝐴2∧𝐴3∧…∧𝐴𝑛$E=A_1\wedge A_2\wedge A_3\wedge \dots \wedge A_n$. You need to find the XOR of the values of all possible unambiguous expressions 𝐸′$E^{\prime }$ which can be obtained from 𝐸$E$ and has at least 𝑘$k$ ∧$\wedge$ symbols used as 𝚇𝙾𝚁$\mathtt{\text{XOR}}$ operation. Since the answer can be very large, you need to find it modulo 2220$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$0$, print 0$0$.

Lost Arithmetic Progression Solution | Codeforces Problem Solution 2022

Power or XOR? Solution | Codeforces Problem Solution 2022 

Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022 

A Perfectly Balanced String? Solution | Codeforces Problem Solution 2022 

Palindrome Basis Solution | Codeforces Problem Solution 2022 

Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022 

Input

The first line of input contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤220,0≤𝑘<𝑛)$(1\le n\le 2^{20},0\le k<n)$.

The second line of input contains 𝑛$n$ integers 𝐵1,𝐵2,…,𝐵𝑛$B_1,B_2,\dots ,B_n$ (1≤𝐵𝑖<220)$(1\le B_i<2^{20})$.

Output

Print a single line containing a binary string without leading zeroes denoting the answer to the problem. If the answer is equal to 0$0$, print 0$0$.

Join Now for Solution:-