LC 1734. 解码异或后的排列

https://leetcode-cn.com/problems/decode-xored-permutation/

这题有点意思，突破口就在于怎么找到 `perm[0]`, 另外这里还有个很重要的限制是n是奇数。

可以试探一下组合 `encoded` 里面的元素，看能够搞出些什么东西来：

所以我们其实可以计算出 perm[0] ^ perm[1], perm[0] ^ perm[2], … perm[0] ^ perm[n-1].

同时n又是奇数，所以如果把上面这些式子放在一起XOR的话，那么就可以得到 `perm[1] ^ perm[2] … perm[n-1]`.

然后我们又知道perm是1到n的排列，所以其实就知道 `perm[0] ^ … perm[n-1]`, 然后在和上面式子进行xor, 就可以得到perm[0]. 

from typing import List
class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        # encoded[i] = perm[i] ^ perm[i+1]

        # get p0^p1, p0^p2 ... p0^p(n-1)
        # them xor all which is p1^p2^...p(n-1) as A
        # then we know 1^2^...n as B
        # then we know p0 = A ^ B


        n = len(encoded) + 1
        B = 0
        for i in range(1, n+1):
            B = B ^ i

        t = 0
        A = 0
        for x in encoded:
            t = t ^ x
            A = A ^ t

        p0 = A ^ B
        ans = [p0]
        t = 0
        for x in encoded:
            t = t ^ x
            ans.append(t ^ p0)
        return ans