题面链接

https://ac.nowcoder.com/acm/contest/23477/H

题面

思路

根据异或运算的性质我们能知道无论如何组合我们经量想让位为1的数量保持不变，那么我们就将问题转化为了在二进制下m的1的数量，然后再将这些1放进n个位置即可，也就是 a n s = n x ans=n^x ans=nx(x表示的是1的数量)

证明

由于在二进制拆位最后同位情况下如果存在不止一个一，那么异或之后的贡献一定小于我们的费用，所以我们要保证对于每一位的个数要么是 0 0 0，要么是 1 1 1，这样的话才能保证 a [ x o r ] = a [ + ] a[xor]=a[+] a[xor]=a[+]，随后我们发现对于每一位来说，他们均不相互干扰，那么他们可能产生的情况便都是n种，所以我们只需要求二进制下 m m m有多少个 1 1 1，随后求