資訊
- ID
- 6
- 時間
- 1000ms
- 記憶體
- 256MiB
- 難度
- 6
- 标签
- 遞交數
- 43
- 已通過
- 3
- 上傳者
暴力枚举不行。
考虑位运算:
即每一位的贡献是多少呢?
我们知道,只有二进制位不同的时候才会对这一位有贡献,所以我们可以对每一位统计这 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,差评