有N个士兵(编号从1到N)。每个士兵都有 M 种不同技能(从 1 到 M 编号)中的一些技能子集。一支军队的技能组合是其组成士兵的技能组合。有多少不同的士兵子集满足特定的技能组合要求
根据 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)
请解释算法。
最佳答案
看了社论自己拿到了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 thatj
ORi
=i
.
如果你觉得难以理解,想想它的物理意义:
For any
i
,j
ORi
=i
iffj
can be produced by take away some binary bit 1 away fromi
例如,如果 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 ORreq
will producereq
你能闻到那个吗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
... wherex
is set of numbers equal toreq
remove one binary bit 1,y
is set of numbers equal toreq
remove two binary bit 1 (orx
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 顺序。
关于algorithm - 动态规划中的包含 - 排除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31401705/