按包含排除计数

Question

>任何人请帮助我弄清楚黑客等级上的蜡烛计数问题中使用的位掩码(包含-排除原则方法(
https://www.hackerrank.com/challenges/candles-2我无法清楚地了解编辑代码中写的内容。您可以打开编辑以获取完整代码

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

这是我可以从您发布的代码中得出的结论-

1( if((mask >> (C[i] - 1)) & 1)检查i根蜡烛的颜色是否已经存在(假设蒙版用于存储已经使用的颜色，因为代码中没有度量(

2( query(H[i] - 1)返回，可以从所有以前的蜡烛形成子序列的数量，因为它们都是彩色的，因为当前蜡烛是第一个具有重复颜色的蜡烛，所以如果排除它，我们会得到"彩色子序列"。

3(update(H[i], dp[i]);用于去除所有不需要的蜡烛。

示例 - 如果我们的序列按顺序具有以下颜色 - 2 3 1 4 5 6 1 7 8然后，当我们到达第二个"1"时，数组中存储的颜色将只有 4 5 6 1，即"2 3 1"将被删除并读取"7 8"。

4( 抱歉madd(tmp, dp[i]);代码中没有足够的数据。

5(__builtin_popcount(mask)计算面具中的一数。