给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。
示例 1：
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2：
输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-xored-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
由于异或和的性质（打表/推导），我们很容易就能在(O(1))内求出来x到y的异或和（当然这个题比较水用不到）。又因为n为奇数，因此可以通过encoded数组求出来(a[2] xor a[3]...xor a[n])，这两者异或就能得到a[1]。知道了a[1]整个排列就都能算出来了。
#include <bits/stdc++.h>
class Solution {
public:
int n, a[100005], e[100005];
int getXor(int start, int x) {//获得从start开始到x的异或和
if(!(start & 1)) {
if(x & 1) {
if(((x - 1) / 2) & 1) return 0;
else return 1;
} else {
if(!((x / 2) & 1)) return x + 1;
else return x;
}
} else {//start为偶数有规律 为奇数的话相当于为偶数的情况再异或以下start
if(x & 1) {
if(((x - 1) / 2) & 1) return 0 ^ start;
else return 1 ^ start;
} else {
if((x / 2) & 1) return (x + 1) ^ start;
else return x ^ start;
}
}
}
vector<int> decode(vector<int>& encoded) {
n = encoded.size() + 1;
int x = 0;
for(int i = 0; i < encoded.size(); i++) {
e[i + 1] = encoded[i];
if(!((i + 1) & 1)) x ^= e[i + 1];
}
vector<int> ret;
int all = getXor(0, n);
a[1] = all ^ x;
for(int i = 2; i <= n; i++) {
a[i] = a[i - 1] ^ e[i - 1];
}
for(int i = 1; i <= n; i++) {
ret.push_back(a[i]);
}
return ret;
}
};