有N个士兵(编号从1到N)。每个士兵都有 M 种不同技能(从 1 到 M 编号)中的一些技能子集。一支军队的技能组合是其组成士兵的技能组合。有多少不同的士兵子集满足有特定技能要求 Problem
根据解释,问题简化为找到这些数字的子集的数量,其 OR 正好等于所需的值,比如 req
令 f(i) 为满足 j OR i = i 的数字 j 的个数,则答案为
∑i(−1)^popcount(i xor req)(2^f(i) −1) 对于所有 i 使得 i OR 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
,一身本事j
.
和
A_1 inter A_2 ... inter A_R
是一组有技能的士兵1,.., R
在他们的团队技能中。
问题提出的问题可以用A_i
表示:
A_1 inter A_2 ... inter A_R
的大小是多少? ?
等于
2^2^R - size( comp(A_1) union comp(A_2) ... union comp(A_R) )
哪里comp(A)
是互补集。
现在,我们可以应用包含排除原则。
还有一个技巧可以让它变得可计算:
如果I
是 {1,..,R}
的子集, 然后是
intersection(comp(A_j) for all j in I)
是I
中没有技能的士兵组(作为一个组) .
请注意,这样一个组中的士兵正是没有任何技能的士兵 I
.
让我们定义 g(I)
作为集合中没有任何技能的士兵数量 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/