排除原则的实施 [英] Exclusion principle implementation

问题描述

我找到了使用 exclusion_principle 来解决<一个href = https://www.hackerrank.com/contests/101hack18/challenges/candles-2 rel = nofollow>问题。我了解其中的大部分内容，但我不明白如何应用排除原则，请帮助我理解它。

I have found a code that uses exclusion_principle to solve a Problem. I understand most part of it but i can't understand how exclusion principle is applied , please help me understand it.

问题
我有一系列元素。每个元素的高度为Hi，颜色为Ci。我必须找到元素序列的数量，这些元素的数量严格按高度增加，并且包含所有可能的颜色（从1到K）。

Problem I have an array of elements. Each element has a height Hi and a colour Ci. I have to find the number of sequences of elements, which are strictly increasing by height and contain all possible colurs (from 1 to K).

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

I can found out the numbers of increasing sequence by using BIT algorithm but the problem is how i fullfill the second condition i.e. each sequence contains at least one element of all the avaliable colours.

示例：（高度

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

推荐答案

I

请考虑一系列不同的，更简单的问题：

Consider a set of different, simpler questions:

取现有颜色1 ... K的适当子集。
当您不允许使用此颜色子集（但不必使用任何颜色）时，可以创建多少合法（根据高度）序列？

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（二进制索引树）。

To answer these questions, it's easy to use BIT (binary indexed tree).

代码用数字 mask 表示范围为<$ c的子集$ c> 0 ... 2 ** K （其中 2 ** K 的计算方式为 1<< ; K ; 0代表整个颜色，因此不应该使用，但请参见下文）。

The code represents a subset by a number mask in the range 0...2**K (where 2**K is calculated as 1 << K; 0 represents the full set of colours, so it should not be used, but see below).

回答原始问题，您必须遍历所有所有颜色子集，并应用包含-排除原则。每个单独的结果都会测量不包含某些颜色的所有序列的集合。因此，所有这些集合的单位都恰好包含不包含任何颜色的元素序列。

To answer the original question, you have to iterate over all subsets of colours, and apply the inclusion-exclusion principle on the results. Each individual result measures the set of all sequences that don't contain some colours. So the untion of all these sets has precisely the sequences of elements that don't contain some colour. And the answer to the original question is a complement of this set.

该代码将计算整个序列集的大小以及所有其他计算结果。从概念上讲，它不属于此处，但是很自然地在同一循环中对其进行计算。

The code calculates the size of the full set of sequences together with all other calculations; conceptually, it doesn't belong there, but it's natural to calculate it in the same loop.

这篇关于排除原则的实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！