企业官网建设流程全解析

题目描述

给你一个长度为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^5
• 1 <= nums[i] <= n
• nums是从1到n的整数的一个排列。

苯人思路

假设化成二进制后最大数有n位，由于组合的全面性，能 cover n 位二进制数的所有情况（n=2时除外）

classSolution{public:intuniqueXorTriplets(vector<int>&nums){intn=nums.size();if(n<=2)returnn;intwei=0;while(n>0){wei++;n/=2;}returnint(pow(2,wei));}};