leetcode 3513. 不同 XOR 三元组的数目 I 中等

给你一个长度为n的整数数组nums其中nums是范围[1, n]内所有数的排列。XOR 三元组定义为三个元素的异或值nums[i] XOR nums[j] XOR nums[k]其中i j k。返回所有可能三元组(i, j, k)中不同的 XOR 值的数量。排列是一个集合中所有元素的重新排列。示例 1输入nums [1,2]输出2解释所有可能的 XOR 三元组值为(0, 0, 0) → 1 XOR 1 XOR 1 1(0, 0, 1) → 1 XOR 1 XOR 2 2(0, 1, 1) → 1 XOR 2 XOR 2 1(1, 1, 1) → 2 XOR 2 XOR 2 2不同的 XOR 值为{1, 2}因此输出为 2。示例 2输入nums [3,1,2]输出4解释可能的 XOR 三元组值包括(0, 0, 0) → 3 XOR 3 XOR 3 3(0, 0, 1) → 3 XOR 3 XOR 1 1(0, 0, 2) → 3 XOR 3 XOR 2 2(0, 1, 2) → 3 XOR 1 XOR 2 0不同的 XOR 值为{0, 1, 2, 3}因此输出为 4。提示1 n nums.length 10^51 nums[i] nnums是从1到n的整数的一个排列。分析异或是不进位加法两个相同的数异或的结果等于 0而 0 异或任何值都等于那个值本身。因此三元组实际上只有取三个不同的数才能得到一个新的数其它情况的值要么是 0要么是其中一个值本身。当 n3 时因为没有三个不同的数因此只能得到 01······n当 n 大于等于 3 时不妨设最大值 n 的取值范围为 [2^k, 2^(k1)-1 )此时可以构造出 01······nn1······ 2^(k1)-1。因此答案为 2^(k1)即大于 n 的最小的 2 的幂。class Solution { public: int uniqueXorTriplets(vectorint nums) { int nnums.size(),maxnnums[0]; if(n3)return n; for(int i1;in;i) maxnmax(maxn,nums[i]); int cnt2; while(cntmaxn)cnt*2; return cnt; } };