c++ - 排除原则实现

Question

我找到了一个使用 exclusion_principle 的代码解决Problem .我明白了大部分，但我不明白如何应用排除原则，请帮助我理解它。

问题我有一个元素数组。每个元素都有一个高度 Hi 和一个颜色 Ci。我必须找到元素序列的数量，它们严格按高度增加并包含所有可能的颜色(从 1 到 K)。

我可以通过使用 BIT 算法找出递增序列的数量，但问题是我如何满足第二个条件，即每个序列至少包含所有可用颜色的一个元素。

示例:(第一列的高度和第二列的颜色)

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);
    }
  }

Answer 1

我不完全了解细节，但这是一个大概的想法。

考虑一组不同的、更简单的问题:

Take some proper subset of the existing colours 1...K. How many legal (according to height) sequences you can make, when you are not allowed to use this subset of colours (but are not obliged to use any colour)?

要回答这些问题，很容易使用 BIT ( binary indexed tree )。

代码用数字mask表示一个子集在 0...2**K 范围内(其中 2**K 计算为 1 << K ；0 代表全套颜色，因此不应使用，但请参阅下文)。

要回答原始问题，您必须遍历所有 颜色子集，并应用 inclusion-exclusion principle在结果上。每个单独的结果测量不包含某些颜色的所有序列的集合。所以所有这些集合的 union 恰好具有不包含某种颜色的元素序列。原始问题的答案是这个集合的补充。

该代码与所有其他计算一起计算完整序列集的大小；从概念上讲，它不属于那里，但很自然地在同一个循环中计算它。