按位与为零的三元组（位运算）

题目

• https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/description/?orderBy=most_votes

思路

• 参考灵神题解，非常易懂，总结一些方法
• 状态压缩常用找下 x 的一个子集（关于1）：for(s = x;s;s = (s - 1) & x)(再加上一个全0的情况)
• 上面的时间复杂度接近$x^2$的，所以先对任意两个数字的与hash会超时，但是换一个方向容易发现n是很小的
• 所以先找一个数字二进制补集的子集，然后再枚举任意两个数字的与，累加

代码

class Solution {
public:
    int countTriplets(vector<int>& nums) {
    int n = nums.size();
    int bit1[1 << 16] = {0};

        bit1[0] = nums.size();
    for(auto x:nums)
        {
            int s = x ^ ((1 << 16) - 1);
    for(int y = s;y;y = (y - 1) & s)
                bit1[y] ++;
        }
        
    int ans = 0;
    for(auto x:nums)
        for(auto y:nums)
            ans += bit1[x&y];
    return ans;
        
    }
};