题解 P6599 【「EZEC-2」异或】
dead_X
·
·
题解
考场心路历程
由于是unrated比赛所以只写了个签到题
5min写完了，难度建议橙/黄
IEE出的题质量还不错/cy
思路简述
首先考虑给定 l 个数，求那个式子的值的情况。
由于位运算位与位之间互不干扰，我们可以考虑按位分析，再计算每一位可以给总答案的贡献。
于是对于每一位，问题转化成了给定 n 个 0 或 1，求那个式子的值。
注意到以下的性质:
- 这些 0 和 1 两两的 xor 值只能是 0 或 1 。
- 上一条性质中取 1 的情况为一个 0 异或一个 1 。
- 对答案的贡献就是取 1 的情况乘以这一位的位值。
显然这一位的贡献就是 2^k\times x\times(l-x) ，其中 2^k 代表所在的二进制位，x 代表这一位 1 (或者 0 ) 的数量，总答案即为各位的贡献和。
那么如果告诉你这些数的最大值，怎么最大化那个式子呢?
还是先看每一位的情况。
在上面的公式中，对于每一位， 2^k 是给定的，那么问题就是 x\times(l-x) 如何最大化?
小学奥数基础知识: x=\frac{l}{2}(2\mid l) 或 x=\frac{(l\pm1)}{2} (2\nmid l) 时取到。
所以我们要保证每一位的 1 数量尽可能靠近 \frac{l}{2} 。
简单的讨论之后发现每一位都可以取到最大值。
构造证明:
设 p 为不大于 n 的最大 2 的自然数次幂数，则
~~然后就做完了~~ 恭喜你，WA了((((((
注意特判 $n=1$ ，因为 $p-1=0$ 取不到，手模一下发现直接输出 $0$ 即可。
## Code
```
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,num=0;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1; ch=getchar();}
while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
return num*f;
}
inline long long readll()
{
long long f=1,num=0;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1; ch=getchar();}
while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
return num*f;
}
int main()
{
int T=read();
++T;
while(--T)
{
long long x=readll(),y=readll(),t=y>>1;
if(x==1)
{
puts("0");
continue;
}
long long now=1LL<<40,res=0;
while(now)
{
now>>=1;
if(x<now) continue;
res+=now*t*(y-t);
}
printf("%lld\n",res%1000000007LL);
}
return 0;
}
```