RainAir
My OI Blog
RainAir
「CF449D」Jzzhu and Numbers

题目大意

有 $n$ 个元素,求有多少个子集满足它们的按位或的答案是 $0$。
$n,a_i \leq 10^6$

题解

其实这篇是来水的因为题目比较简单
答案是 $0$ 也就是每一位都是 $0$,发现 $log_2(10^6) \approx 19.9315685693 \leq 20$ ,所以我们可以对于每一位分别容斥。我们现在容斥枚举一个 $S$ 需要求出 $S$ 的位置一定填 $1$,其他位置无限制的方案数。我们将每个数也看成一个状压的01 集合的话,设 $f_{s}$ 表示集合 $s$ 出现的次数,也就是求

$$\sum_{s1 \supseteq S} f_{s1}$$

也就是 $S$ 的超集和,这个可以用高维前缀和轻松解决。
时间复杂度 $O(nlogn)$

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/808
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF449D」Jzzhu and Numbers
题目大意 有 $n$ 个元素,求有多少个子集满足它们的按位或的答案是 $0$。 $n,a_i \leq 10^6$ 题解 其实这篇是来水的因为题目比较简单 答案是 $0$ 也就是每一位都是 $0$,发现 $log_2(1…
扫描二维码继续阅读
2019-08-28
标签
近期评论