# 982.按位与为零的三元组 (Hard)

## 问题描述
[982. 按位与为零的三元组 (Hard)](https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/)

给你一个整数数组 `nums` ，返回其中 **按位与三元组** 的数目。

**按位与三元组** 是由下标 `(i, j, k)` 组成的三元组，并满足下述全部条件：

- `0 <= i < nums.length`
- `0 <= j < nums.length`
- `0 <= k < nums.length`
- `nums[i] & nums[j] & nums[k] == 0` ，其中 `&` 表示按位与运算符。

**示例 1：**

```
输入：nums = [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

```

**示例 2：**

```
输入：nums = [0,0,0]
输出：27

```

**提示：**

- `1 <= nums.length <= 1000`
- `0 <= nums[i] < 2¹⁶`

## 解题思路
可以先用哈希表`ump`存储`nums[i] & nums[j]`的结果，再与`nums[k]`按位与，如果结果为0，`res += ump[nums[i] & nums[j]]`。

优化，我们把二进制看成集合，二进制从低到高第`i`位为1表示`i`在集合中，为0表示`i`不在集合中，例如$a = 1101_{(2)}$表示集合$A=\{0,2,3\}$；

那么，$a \& b = 0$即集合$A$和集合$B$没有交集，或者说$B$是集合$\complement_U A$，这里$U=\{0,1,2,...,15\}$，对应的数字即$0xffff$，一个数异或$0xffff$就能得到这个数的补集；

所以，代码可以优化成枚举$m = nums[k]\oplus 0xffff$的子集；

要枚举$m$的子集$s$，可以将$s$从$m$不断减一直到0，如果$s \& m = s$，说明$s$是$m$的子集；

更高效的做法是直接“跳到”下一个子集，即$s$更新为$(s - 1)\& m$，这样做的正确性在于，$s-1$只把$s$最低位的$1$改成了$0$（考虑$s$对应的集合），比这个$1$更低的$0$全都变成了$1$，因此下一个子集，一定是$s-1$的子集，直接$\&m$，就能得到下一个子集；

最后，当$s=0$时，由于$-1$的二进制全为$1$，所有$(s-1)\&m = m$，所以我们可以判断下一个子集是否又回到$m$，来判断是否要退出循环。

> 注：这一技巧常用于子集状态压缩DP中

## 代码
```cpp
class Solution {
public:
    int countTriplets(vector<int> &nums) {
        int cnt[1 << 16]{};
        for (int x : nums)
            for (int y : nums)
                ++cnt[x & y];
        int ans = 0;
        for (int m : nums) {
            m ^= 0xffff;
            int s = m;
            do { // 枚举 m 的子集（包括空集）
                ans += cnt[s];
                s = (s - 1) & m;
            } while (s != m);
        }
        return ans;
    }
};
```