自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:22:19，当前版本为作者最后更新于2020-06-06 23:23:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考场心路历程

由于是unrated比赛所以只写了个签到题

5min写完了，难度建议橙/黄

IEE出的题质量还不错/cy

思路简述

首先考虑给定 $l$ 个数，求那个式子的值的情况。

由于位运算位与位之间互不干扰，我们可以考虑按位分析，再计算每一位可以给总答案的贡献。

于是对于每一位，问题转化成了给定 $n$ 个 $0$ 或 $1$，求那个式子的值。

注意到以下的性质:

1. 这些 $0$ 和 $1$ 两两的 $xor$ 值只能是 $0$ 或 $1$ 。
2. 上一条性质中取 $1$ 的情况为一个 $0$ 异或一个 $1$ 。
3. 对答案的贡献就是取 $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$ 的自然数次幂数，则

$\frac{l}{2}(2\mid l)$ 或 $\frac{(l\pm1)}{2} (2\nmid l)$ 个数取 $p$ ， 剩下的取 $p-1$ 即可。

然后就做完了 恭喜你，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;
}