1 条题解
-
0
30pts
枚举所有情况进行判定,时间复杂度为
+30pts
对于 , 表示考虑了序列的前 个数,其中 集合中所有元素的或运算为 , 集合中所有元素的或运算为 的方案数,其中 ,背包进行转移,时间复杂度为 。
100pts
对于二进制下某一位 ,若满足第 位上为 的 个数不为 个,那么所有第 位上为 的数不能划分在同一个集合。
例如对于 这三个数, 一定不能被划分在同一个集合,否则另一个集合的最低位一定为 ,不满足题设条件。
所有第 位上为 的数不能划分在同一个集合并不好处理,我们考虑其相反面进行容斥,所有第 位上为 的数都应当划分在同一个集合并不好处理
考虑容斥,强制钦定第 位上为 的数划分在同一个集合。
现在有若干数强制钦定在同一个集合,将这些数用并查集连接,在同一个并查集里的数说明一定要被分配在一个集合里,考虑乘法原理,每个并查集的联通块都有 种可能,即划分在 或 ,那么方案数即为 ,
容斥一共有 种情况。
对于每一种情况,需要进行 的判断,但所有数最多合并到同一个并查集里,并查集部分的复杂度为,复杂度为。
- 1
信息
- ID
- 134
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者