有N名士兵（从1到N）。每个士兵都有m种不同技能（从1到m）中的一些技能子集。军队的技能集是组成军队的士兵技能集的联合体。有多少不同的兵种满足特定的技能要求
Problem
根据解释问题，归结为求出这些数的子集的个数，这些子集的or正好等于所需的值，例如req
设f（i）为数字j的个数，使得j或i=i。那么答案是∑i（－1）^popcount（i xor req）（2^f（i）－1）对于所有i，使得i或req是req
这个公式是怎么来的，popcount如何描述它的加或减。
最佳答案
这是我的看法。解决问题的方法是：不要对拥有某种技能的小组进行推理，
让我们来解释一下那些没有某种技能的士兵。
因为第二个属性可以很好地从组传播到所有成员。
在我们开始之前，先简单一点：
在不丧失一般性的情况下，我们可以筛选出至少有一项技能在所需范围之外的士兵。因为一个子集的技能必须是所需的技能，所以永远不需要那些知道太多的聪明士兵。
从现在起，我们假设所需的技能集是{1, ... , R}，并且士兵的技能介于1和R之间。
我们需要定义A_i（其中i属于{1,..,R}）：A_i：在其组技能集中具有技能的一组士兵。
换句话说，i中的一个组（A_i表示交叉点）是指至少有一名士兵具有技能编号inter的组。
现在如果i，i<j=在其组技能集中具有A_i inter A_j和i技能的士兵组。
换句话说，j中的一个组是具有至少一个属性的组
一名同时拥有A_i inter A_j和i技能的士兵。
两名士兵，一名技能j，一名技能i。
以及
A_1 inter A_2 ... inter A_R
是一组士兵，他们的组技能集中确实有技能
j。问题提出的问题可以用
1,.., R表示：A_i的大小是多少？等于
2^2^R - size( comp(A_1) union comp(A_2) ... union comp(A_R) )
其中
A_1 inter A_2 ... inter A_R是互补集。现在，我们可以应用包含排除原则。
还有一个诀窍可以让它变得可计算：
如果
comp(A)是I的s子集，则intersection(comp(A_j) for all j in I)
是指在
{1,..,R}中没有技能的士兵（作为一个整体）。请注意，这样一个组中的士兵正是没有
I技能的士兵。将
I定义为在集合g(I)中没有任何技能的士兵的数量。有了这个，我们size( intersection(comp(A_j) for all j in I) ) = 2^g(I)
最后，我得到的结果是：
2^2^R - sum( (-1)^(size(I)+1) * 2^g(I) , for each I subset of {1,..,R} and I non-empty)
我希望这能有帮助。如果还不清楚，请告诉我。
关于algorithm - 包含与排除的动态规划技术，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31390568/