动态规划中的包含 - 排除

Question

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

问题链接

根据解释问题减少到找到这些数字的子集的数量,其OR正好等于所需的值,比如req

令f(i)为数j的数量,使得j OR i = i.

然后答案是
Σ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后，我认为理解“包含-排除原则”在这里的应用并不是那么容易，这个问题是围绕Codeforces Div.1 Problem C / D级别的，例如这个：http://codeforces.com/contest/449/problem/D

重写版本@2016

之前的答案太乱了，我尝试清理它并重写一个更具可读性的答案

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

大局解释

首先，不要过度思考问题，给定a[1..N]，解决方案实际上是可以产生的所有子集req

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

设为满足OR = 的f(i)数字个数。jii

如果你觉得很难理解，想想它的物理意义：

对于任何i， jOR i= i iff可以通过 去掉一些二进制位 1 来j生成 i

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

所以，确实是当 OR 时2^f(i) - 1可以产生的可能子集的数量ii

请稍等一下，确保您首先完成了上述部分。

现在 if i=req本身怎么办？这是什么意思？哪些子集被计入2^f(req)-1？2^f(req)-1与我们想要的答案有何关系？

我们想要 OR 所有元素将产生的子集数量req

2^f(req)-1req给出 OR 所有元素 OR将产生的子集的数量req

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

像这样思考：有一些子集2^f(req)-1计数，这些子集或所有元素只能产生x其中x可以通过从中删除一些二进制位 1 来产生req（参见上面的块引用）

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

假设我们要减去那些 OR 所有元素等于 的子集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！

根据包含-排除原则，你必须将它们添加回来......让我们在这里做一个小总结：

我们想要的是2^f(req)-1 - 2^f(x)-1 + 2^f(y)-1... 其中x是一组数字等于req删除一个二进制位 1,y是一组数字等于req删除两个二进制位 1 （或x删除一个二进制位 1）

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

对于所有i<= req，的每一位要么与 0i相同req，然后i xor req等于req - i（删除 的所有 1 位i）， 因此popcount(i xor req)确实给出了要从中删除的二进制位 1 的 # 以req获得i

结合整个故事，形成公式：Sum (-1)^popcount(i xor req) * (2^f(i) - 1)对于所有i这样的i OR req = req

DP 计算 f(i)

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本身 + f(某个 j ，即我删除一些位 1)

因此，如果 i 的第 j 位为 1，则 f(i) = 1 + f(i xor (1 << j))

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