[1734] Decode XORed Permutation

又是一個，沒看解答不會寫，說穿了不稀奇的玩意兒......

前身是上一題（比樓下）

這一題的難點就是要怎麼推導出第一個數

討論區有人寫的很清楚，

假設現在是 array[0,1,2,3]

它們會是 n=5 , 長度加一的 1~n 去組起來的，n必定是奇數

所以設一個total XOR 會是 1^2^3^.....^(n-1)^n

原本的array 會是 1~n 兩兩XOR起來，只是我們不知道它的排序。先用長度4的array 

n=5 來假設，設 1~n 為 a,b,c,d,e

則 

array[0]  是 a^b

array[1]  是 b^c

array[2]  是 c^d

array[3]  是 d^e

total XOR =  a^b^c^d^e

a= (totalXOR) ^ (b^c) ^ (d^e) = ( a^b^c^d^e ) ^ (b^c) ^ (d^e) =

(totalXOR) ^ array[1] ^ array[3]

一個數 ^ 自己會消掉（變成0)，所以上面這個算式會倆倆消掉，剩下a 自己

如此就可以求出第一個數了!!! 得到第一個數以後，這題就等於 1720. Decode XORed Array 了

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* decode(int* encoded, int encodedSize, int* returnSize){

*returnSize = encodedSize+1;

int n = encodedSize+1;

int *ret= calloc (n, sizeof(int));

int totalXor=0;

for (int i=1;i<=n;i++)

totalXor ^= i;

for (int i=1;i<encodedSize;i+=2)

ret[0] ^= encoded[i];

ret[0] ^= totalXor;

// printf("%d\n", ret[0]);

for (int i=0; i<encodedSize; i++)

ret[i+1] = encoded[i] ^ ret[i];

return ret;

}