原文链接: https://leetcode-cn.com/problems/triples-with-bitwise-and-equal-to-zero

英文原文

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

 

Example 1:

Input: nums = [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Example 2:

Input: nums = [0,0,0]
Output: 27

 

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 216

中文题目

给定一个整数数组 A，找出索引为 (i, j, k) 的三元组，使得：

• 0 <= i < A.length
• 0 <= j < A.length
• 0 <= k < A.length
• A[i] & A[j] & A[k] == 0，其中 & 表示按位与（AND）操作符。

 

示例：

输入：[2,1,3]
输出：12
解释：我们可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

 

提示：

1. 1 <= A.length <= 1000
2. 0 <= A[i] < 2^16

通过代码

高赞题解

高维前缀和处理出来，之后枚举前两个，最后一个直接从高维前缀和里面取出来

class Solution {
public:
	int w = 0;
	int N, B[1 << 16];

	int countTriplets(vector<int>& A) {
		N = A.size();
		for (auto a : A)
		{
			B[a]++;
			while ((1 << w) <= a)w++;
		}

		for (int i = 0; i<w; i++) {
			for (int j = 0; j<(1 << w); j++) {
				if (j&(1 << i)) B[j] += B[j ^ (1 << i)];
			}
		}

		int ans = 0;
		int mask = (1 << w) - 1;
		for (int i = 0; i < N; i++)
			for (int j = 0; j <= i; j++)
				ans += B[~(A[i] & A[j])&mask] << (i != j);
		return ans;
	}
};

快速沃尔什变换模板题，没啥好说的

// FWT
class Solution {
public:
	int w;
	int B[1 << 16];
	void FWTand(int *a, int opt)
	{
		int N = 1 << w;
		for (int mid = 1; mid < N; mid <<= 1)
			for (int R = mid << 1, j = 0; j < N; j += R)
				for (int k = 0; k < mid; k++)
					if (opt == 1) a[j + k] += a[j + k + mid];
					else a[j + k] -= a[j + k + mid];
	}
	int countTriplets(vector<int>& A) {
		for (auto a : A)
		{
			B[a]++;
			while ((1 << w) <= a)w++;
		}
		FWTand(B, 1);
		for (int i = 0; i<(1 << w); i++) B[i] *= B[i] * B[i];
		FWTand(B, -1);
		return B[0];
	}
};

统计信息

通过次数	提交次数	AC比率
2670	4857	55.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言