集合计数
题意:
求 [0,2n−1]内中选择任意数量 (不能不选) 的几个不同的数,它们按位与后有 k个 1的方案数。
分析:
我们首先定义一个比较容易计算的函数,g[x],以及我们需要求的函数 f[x]。f[x]表示 “恰有 x 个 1 出现在最终的结果中” 的方案数。
如果我们枚举哪几个位是最终的 1,剩下的位情况不确定,这样可以获得。可以得到:
g[x]=Cxn(2(2n−x)−1)
上面这个式子的原理是:包含了这 x个 1的数字总共有 2n−x个,每个都可以选或者不选,但不能一个都不选,因此共 22n−x−1种选法。另外,枚举的这几个 1的位置不同,也对应这不同的情况,因此需要乘一个组合数。
但是,g[x]并不是一个确切的值,并不是我们常说的 “至少 x 个 1” 的方案数。可以说,它重复计算了很多东西。比如,011和 111的按位与结果为 011,但是这一种情况在 g[001]和 g[010]中都出现了,因此 g[2]=g[001]+g[010]中这种情况出现了两次。不难发现,如果一种情况的按位与结果有 x个 1,那么它在 g[y]中一定出现了 Cyx次。
所以,我们可以直接建立起 f和 g的关系:
g[x]=n∑i=xCxif[i]
根据二项式反演:
f[x]=n∑i=x(−1)i−xCxig[i]
0 条评论