c++ - 排除原则的实现

我找到了一个使用exclusion_principle解aProblem的代码我理解其中的大部分，但我不明白排除原则是如何应用的，请帮助我理解它。
问题
我有一组元素每个元素都有一个高度Hi和一个颜色Ci我必须找到元素序列的数量，它们严格地按高度递增，包含所有可能的元素（从1到k）。
我可以用位算法找出递增序列的个数，但问题是如何满足第二个条件，即每个序列至少包含所有可用颜色中的一个元素。
示例：（第一列为高度，第二列为颜色）

4 3
1 1
3 2
2 2
4 3

两个有效的子序列是（1，2，4）和（1，3，4）
代码：

int res = 0;
  for(int mask = 0; mask < (1 << K); mask ++){
    memset(ft, 0, sizeof ft);
    int tmp = 0;
    for(int i = 0; i < N; i++){
      if((mask >> (C[i] - 1)) & 1){
        dp[i] = 1 + query(H[i] - 1); // BIT Query function
        madd(tmp, dp[i]);
        update(H[i], dp[i]); // BIT update function
      }
    }
    if(__builtin_popcount(mask) % 2 == K % 2){
      madd(res, tmp);
    } else {
      madd(res, mod - tmp);
    }
  }

最佳答案

我不完全了解细节，但这里有一个大致的想法。
考虑一组不同的、更简单的问题：
采取一些适当的子集现有的颜色1…K。
当你不允许使用这部分颜色（但没有义务使用任何颜色）时，你可以制作多少个合法的（根据高度）序列？
要回答这些问题，使用bit（binary indexed tree）很容易。
该代码用数字表示mask范围内的子集（其中0...2**K计算为2**K；0表示全套颜色，因此不应使用，但请参见下文）。
要回答原始问题，您必须迭代所有颜色子集，并对结果应用inclusion-exclusion principle。每一个单独的结果都测量不包含某些颜色的所有序列集。因此，所有这些集合的解开都精确地具有不包含某种颜色的元素序列原问题的答案是这一套的补充。
代码将计算整个序列集的大小以及所有其他计算；从概念上讲，它不属于那里，但在同一个循环中计算它是很自然的。

关于c++ - 排除原则的实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27428187/