信息
- ID
- 6
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 42
- 已通过
- 2
- 上传者
暴力枚举不行。
考虑位运算:
即每一位的贡献是多少呢?
我们知道,只有二进制位不同的时候才会对这一位有贡献,所以我们可以对每一位统计这 n 个数有多少的 0 多少的 1 ,我们让 0,1 两两匹配,最后算上贡献加起来就是了。
$$ans=\sum_{i=0}^{60}2^i \times (cnt_{i,0}\times cnt_{i,1}) $$cnti,0 是第 i 位是 0 的个数
cnti,1 是第 i 位是 1 的个数
注意答案还要乘2.
枚举60位让我爆int,差评