2 条题解
信息
- ID
- 27
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 794
- 已通过
- 241
- 上传者
显然,对于正整数 p,q,设 p,q 在二进制表示下的位数分别为 x,y,若 p≤q,则:
要注意,对于任意非负整数 m,都满足 0≤0⊕m≤m,所以需要特判 0。
在特判 0 后,我们可以把剩下的元素从小到大排序,开一个桶,把枚举过的数在二进制表示下的位数记录在桶里,动态地根据上面的讨论计算即可。
时间复杂度 O(nlogn+nlogV),其中 V 为值域。