【位运算 子集状态压缩】982按位与为零的三元组

算法可以发掘本质，如：

一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。

二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。

三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。

四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。

一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

位运算 子集状态压缩

LeetCode982. 按位与为零的三元组

给你一个整数数组 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¹⁶

子集状态压缩

∀ \forall∀i,nums[i]∈ \in∈[0,2¹⁶)，故nums[i1]&nums[i2] ∈ \in∈[0,2¹⁶)。vIj[x] 记录， nums[i]&nums[j]为x的数量。

然后枚举k，不用枚举所有x，只需要使用子集压缩的技巧，枚举nums[k]的补集的子集。

时间复杂度: O(nn)+O(2¹⁶n) n = nums.length。

代码

核心代码

class Solution {
public:
  int countTriplets(vector<int>& nums) {
    vector<int> vij(1 << 16);
    for (const auto& n1: nums) {
      for (const auto& n2 : nums) {
        vij[n1 & n2]++;
      }
    }
    int iRet = vij[0]* nums.size();
    for (const auto& n : nums) {
      const int mask = (~n)&((1<<16)-1);
      for (int sub = mask; sub; sub = (sub - 1) & mask) {
        iRet += vij[sub];
      }
    }
    return iRet;
  }
};

测试用例

int main()
{ 
  vector<int> nums;
  {
    Solution sln;
    nums = { 2,1,3 };
    auto res = sln.countTriplets(nums);
    Assert(12, res);
  }
  {
    Solution sln;
    nums = { 0,0,0 };
    auto res = sln.countTriplets(nums);
    Assert(27, res);
  }
  
  
}

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。