[Solution] Power or XOR? solution codeforces

Power or XOR? solution codeforces – The symbol  is quite ambiguous, especially when used without context. Sometimes it is used to denote a power (𝑎𝑏=𝑎𝑏a∧b=ab) and sometimes it is used to denote the XOR operation (𝑎𝑏=𝑎𝑏a∧b=a⊕b).

[Solution] Power or XOR? solution codeforces

You have an ambiguous expression 𝐸=𝐴1𝐴2𝐴3𝐴𝑛E=A1∧A2∧A3∧…∧An. You can replace each  symbol with either a 𝙿𝚘𝚠𝚎𝚛Power operation or a 𝚇𝙾𝚁XOR operation to get an unambiguous expression 𝐸E′.

The value of this expression 𝐸E′ is determined according to the following rules:

  • All 𝙿𝚘𝚠𝚎𝚛Power operations are performed before any 𝚇𝙾𝚁XOR operation. In other words, the 𝙿𝚘𝚠𝚎𝚛Power operation takes precedence over 𝚇𝙾𝚁XOR operation. For example, 4𝚇𝙾𝚁6𝙿𝚘𝚠𝚎𝚛2=4(62)=436=324XOR6Power2=4⊕(62)=4⊕36=32.
  • Consecutive powers are calculated from left to right. For example, 2𝙿𝚘𝚠𝚎𝚛3𝙿𝚘𝚠𝚎𝚛4=(23)4=84=40962Power3Power4=(23)4=84=4096.

You are given an array 𝐵B of length 𝑛n and an integer 𝑘k. The array 𝐴A is given by 𝐴𝑖=2𝐵𝑖Ai=2Bi and the expression 𝐸E is given by 𝐸=𝐴1𝐴2𝐴3𝐴𝑛E=A1∧A2∧A3∧…∧An. 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  symbols used as 𝚇𝙾𝚁XOR operation. Since the answer can be very large, you need to find it modulo 22202220. Since this number can also be very large, you need to print its binary representation without leading zeroes. If the answer is equal to 00, print 00.

Input

The first line of input contains two integers 𝑛n and 𝑘k (1𝑛220,0𝑘<𝑛)(1≤n≤220,0≤k<n).

The second line of input contains 𝑛n integers 𝐵1,𝐵2,,𝐵𝑛B1,B2,…,Bn (1𝐵𝑖<220)(1≤Bi<220).

[Solution] Power or XOR? solution codeforces

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

Examples
input

Copy
3 2
3 1 2
output

Copy
1110
input

Copy
3 1
3 1 2

[Solution] Power or XOR? solution codeforces

output

Copy
1010010
input

Copy
3 0
3 1 2
output

Copy
1000000000000000001010010
input

Copy
2 1
1 1
output

Copy
0

Power or XOR? solution codeforces

For each of the testcases 11 to 33𝐴={23,21,22}={8,2,4}A={23,21,22}={8,2,4} and 𝐸=824E=8∧2∧4.

For the first testcase, there is only one possible valid unambiguous expression 𝐸=824=14=(1110)2E′=8⊕2⊕4=14=(1110)2.

For the second testcase, there are three possible valid unambiguous expressions 𝐸E′:

  • 824=148⊕2⊕4=14
  • 824=644=6882⊕4=64⊕4=68
  • 824=816=248⊕24=8⊕16=24

XOR of the values of all of these is 146824=82=(1010010)214⊕68⊕24=82=(1010010)2.For the third testcase, there are four possible valid unambiguous expressions 𝐸E′:

  • 824=148⊕2⊕4=14
  • 824=644=6882⊕4=64⊕4=68
  • 824=816=248⊕24=8⊕16=24
  • (82)4=644=224=16777216(82)4=644=224=16777216

XOR of the values of all of these is 14682416777216=16777298=(1000000000000000001010010)214⊕68⊕24⊕16777216=16777298=(1000000000000000001010010)2.For the fourth testcase, 𝐴={2,2}A={2,2} and 𝐸=22E=2∧2. The only possible valid unambiguous expression 𝐸=22=0=(0)2E′=2⊕2=0=(0)2.

 

For Solution

Click here

Leave a Comment