algorithm - 动态规划中的包含 - 排除

Question

有N个士兵(编号从1到N)。每个士兵都有 M 种不同技能(从 1 到 M 编号)中的一些技能子集。一支军队的技能组合是其组成士兵的技能组合。有多少不同的士兵子集满足特定的技能组合要求

Problem Link

根据 Explanation 问题简化为找到这些数字的子集的数量，其 OR 恰好等于所需的值，比如 req

令 f(i) 为满足 j OR i = i 的数 j 的个数。

则答案为
∑i(−1)^popcount(i xor req)(2^f(i)−1) 对于所有 i 使得 i OR req 是 req

请解释上面的公式和它是怎么来的

我知道选择N个元素的方法数是(2^n-1)但是为什么这个词(−1)^popcount(i xor req)

请解释算法。

Answer 1

看了社论自己拿到了AC，我觉得这里的“Inclusion-Exclusion Principle”的应用不是那么容易理解的，这道题围绕Codeforces Div.1 Problem C/D level，比如，这个:http://codeforces.com/contest/449/problem/D

重写版本@2016

Previous answer is too messy, I try to clean it up and rewrite a more readable answer

我将解释为什么该解决方案有效，但不是 如何提出这样的解决方案，我认为这更多的是经验。

大图解释

首先，不要想太多这个问题，鉴于 a[1..N] ，解决方案实际上是 所有可以产生 req 的子集

话虽如此，我们如何找到所有可以产生x的子集？ ？如解决方案所示，让我们定义 f(i)

Let f(i)be the number of numbers such that j OR i = i.

如果你觉得难以理解，想想它的物理意义:

For any i, j OR i = i iff j can be produced by take away some binary bit 1 away from i

例如，如果 i = 7，然后 j可以是 0,1,2...,7；如果i =5，那么j可以是 0,1,4,5

所以，2^f(i) - 1确实是可以产生i的可能子集的#当或 i

稍等片刻，确保您先完成上述部分。

现在如果 i 会怎样= req本身？这是什么意思？ 2^f(req)-1 中计算了哪些子集？ 2^f(req)-1如何与我们想要的答案有关？

We want the # of subsets which OR all elements will produce req

2^f(req)-1 gives the # of subsets which OR all elements OR req will produce req

你能闻到那个吗2^f(req)-1可能比我们需要的更多？

这样想:有一些子集2^f(req)-1计数，其中 OR 所有元素只能产生 x其中 x可以通过从 req 中删除一些二进制位 1 来生成(参见上面的 block 引用)

所以，我们必须从 2^f(req)-1 中减去一些东西，这里出现了包容-排除原则。

假设我们要减去那些或所有元素等于 x 的子集，即 req取走一位二进制位1

有了类似的想法，你会发现你要减去2^f(x)-1 , 对于所有可能的 x ，在这里，记住 x是所有数字 req取走一个二进制位1

但是，你会比你应该减去更多，因为不同的x可能共享相同的 y , 其中y是req去掉两个二进制位1，即y是x拿走一个二进制位 1，你应该为每个 y 恰好删除一次来自 2^f(req)-1 , 但在减去 2^f(x)-1 的过程中，对于某些 y，您有多次减号!

根据包容排除原则，你必须把它们加回来......让我们在这里做一个小总结:

What we want is 2^f(req)-1 - 2^f(x)-1 + 2^f(y)-1 ... where x is set of numbers equal to req remove one binary bit 1, y is set of numbers equal to req remove two binary bit 1 (or x remove one binary bit 1)

你能看出这里的规律吗？是的，就是 -1^popcount()公式中的部分

对于所有i <= req , i 的每一点与 req 相同或 0，然后是 i xor req等于req - i (删除 i 的所有 1 位)，所以 popcount(i xor req)确实给出了要从 req 中删除的二进制位 1 的#为了得到i

综合原委，形成公式:Sum (-1)^popcount(i xor req) * (2^f(i) - 1)对于所有 i这样 i OR req = req

计算f(i)的DP

for(int i=0;i<20;i++)  
    for(int j=0; j<=(1<<20); j++) {  
         if(j&(1<<i)) {  
             f[j] += f[j^(1<<i)];  
         }  
    }

这里是要计算的DP部分f(i)

请注意，它基于以下递推关系:

f(i) = i itself + f(some j which is i remove some bit 1)

So, f(i) = 1 + f(i xor (1 << j)) if i's j-th bit is 1

请注意 i xor (1<<j)必须小于 i ，因此是 DP 顺序。