Lost Array solution codeforces – A long time ago, Spyofgame invented the famous array 𝑎a (11-indexed) of length 𝑛n that contains information about the world and life. After that, he decided to convert it into the matrix 𝑏b (00-indexed) of size (𝑛+1)×(𝑛+1)(n+1)×(n+1) which contains information about the world, life and beyond.
[Solution] Lost Array solution codeforces
Spyofgame converted 𝑎a into 𝑏b with the following rules.
- 𝑏𝑖,0=0bi,0=0 if 0≤𝑖≤𝑛0≤i≤n;
- 𝑏0,𝑖=𝑎𝑖b0,i=ai if 1≤𝑖≤𝑛1≤i≤n;
- 𝑏𝑖,𝑗=𝑏𝑖,𝑗−1⊕𝑏𝑖−1,𝑗bi,j=bi,j−1⊕bi−1,j if 1≤𝑖,𝑗≤𝑛1≤i,j≤n.
Here ⊕⊕ denotes the bitwise XOR operation.
Today, archaeologists have discovered the famous matrix 𝑏b. However, many elements of the matrix has been lost. They only know the values of 𝑏𝑖,𝑛bi,n for 1≤𝑖≤𝑛1≤i≤n (note that these are some elements of the last column, not the last row).
The archaeologists want to know what a possible array of 𝑎a is. Can you help them reconstruct any array that could be 𝑎a?
The first line contains a single integer 𝑛n (1≤𝑛≤5⋅1051≤n≤5⋅105).
The second line contains 𝑛n integers 𝑏1,𝑛,𝑏2,𝑛,…,𝑏𝑛,𝑛b1,n,b2,n,…,bn,n (0≤𝑏𝑖,𝑛<2300≤bi,n<230).
[Solution] Lost Array solution codeforces
If some array 𝑎a is consistent with the information, print a line containing 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an. If there are multiple solutions, output any.
If such an array does not exist, output −1−1 instead.
3 0 2 1
1 2 3
1 199633
199633
[Solution] Lost Array solution codeforces
10 346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607
725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365
If we let 𝑎=[1,2,3]a=[1,2,3], then 𝑏b will be:
| 00 | 11 | 22 | 33 |
| 00 | 11 | 33 | 00 |
| 00 | 11 | 22 | 22 |
| 00 | 11 | 33 | 11 |