自动搬运

查看原文

来自洛谷，原作者为

	chlchl AFOed.

搬运于2025-08-24 22:43:58，当前版本为作者最后更新于2023-01-16 13:53:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

唯一打出正解的题，还是得写篇东西纪念一下（主要是这场比赛是拉满比赛分的关键一场）。

题意

求构造一个长度为 $n$ 的序列，每个数都在 $[1,m]$ 之间，使得前缀、后缀异或和均递增。

Solution

这个题非常像 CF 的 A，构造的签到题。

首先有个贪心的结论，只要我们能够知道最大数的最小值，就能快速判断是否能构造。

考虑异或和持续变大是什么情况。每次异或和若想变大，显然需要将高位的某一位变成 $1$。以此类推，$n$ 个数的异或和要想递增，至少需要有 $n$ 位是 $1$，这个结果肯定是最小的。

考虑当刚好 $n$ 位是 $1$，即前 $n$ 个数的异或和为 $2^n-1$ 时，每个数是什么。显然每一个数只能够是 $2^i$，因为一共只有 $n$ 位是 $1$，所以每个数都只能够有一位是 $1$。

题目要求递增，我们就令 $a_i=2^{i-1}$，注意 $1=2^0$，也是符合条件的。

由于异或和只是一个 $0,1$ 变换的过程，而且按上面的构造，$1$ 之间的位置是不影响的，所以只要前缀和递增，后缀和显然也是递增的。

判断无解也很简单，如果 $2^{n-1}>m$，就无解了。

但是注意这东西似乎不能用位运算，$2^{100000}$ 会炸掉，有两种解决方案：一种是使用 __lg 函数反向判断（考场用的 log2，hack 添加之后就丢精了），即 $\log_2m+1$ 和 $n$ 的大小关系；第二种是特判，如果 $n>63$ 必定无解（$m\leq 2^{63}-1$）。

就喜欢 T1 放这种诈骗了又好像没有诈骗的题目 qwq。

#include<bits/stdc++.h>
using namespace std;

int T, n;
long long m;

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%lld", &n, &m);
		if(__lg(m) + 1 >= n){
			printf("Yes\n");
			for(int i=0;i<n;i++)
				printf("%lld ", (1ll << i));
			printf("\n");
		}
		else
			printf("No\n");
	}
	return 0;
}