自动搬运

查看原文

来自洛谷，原作者为

	JuRuoOIer CSP-S2024 打炸并被卡勾七线的初中牲

搬运于2025-08-24 22:44:47，当前版本为作者最后更新于2023-02-04 15:18:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解 P9033 「KDOI-04」XOR Sum

UPD：介绍异或的部分及数据范围部分均按要求进行了调整。

好吧又是赛时唯一 AC 的题目……

Part1 题意

原题传送门

• 给定 $n,m,k$，要求构造一个非负整数序列，长度为 $n$，所有项均不超过 $m$，且异或和为 $k$。
• $1 \le T \le 1000$，$1 \le \sum n \le 2 \times 10^5$，$0 \le m,k \le 10^8$。

Part2 思路

2-1 关于异或

首先大家要知道异或是什么。

异或有一个外号，叫做不进位加法，因为 $0\ \text{xor}\ 0 = 0$，$1\ \text{xor}\ 1=0$，$0\ \text{xor}\ 1=1$（$0+0$ 和 $1+1$ 二进制最后一位均为 $0$）。

于是我们得出：任何数异或 $0$ 等于其本身。这条性质记好了，后面会用到。

2-2 判无解、凑答案

接着我们看怎么得到 $k$。

既然 $k$ 只能通过不超过 $m$ 的数字异或得到，所以 $k$ 的二进制位数不能超过 $m$ 的二进制位数（显然异或没法变出新的位），即 $\lceil\log_2k\rceil \le \lceil\log_2m\rceil$，否则无解。

接下来分两种情况考虑：

• 当 $k \le m$ 时，只需要第一项赋值为 $k$，其余项均为 $0$ 即可（还记得 2-1 中的性质吗？）。
• 当 $k > m$ 时，又由于 $\lceil\log_2k\rceil \le \lceil\log_2m\rceil$，所以 $k$ 和 $m$ 位数相同。也就是说，$k$ 与 $m$ 二进制下最高位是同一位且都是 $1$。
  • 然后我们把 $k$ 最高位上的 $1$ 去掉，此时 $k$ 一定小于 $m$（因为位数减少了），一项就可以完成。
  • 而刚才去掉的 $1$ 实际上就是 $100...00$（长度同 $k,m$），一定不会超过 $m$，也需要一项完成。
  • 由于是同一个数字拆出来的，所以它们不可能在同一个位置均为 $1$。也就是说，它们两个的异或等于它们的和 $k$。

于是 $k>m$ 的情况就解决了：$n=1$ 无解，否则将 $k$ 像上面那样分成两份，后面填 $0$ 即可。

Part3 代码

注释在代码里啦！

#include<bits/stdc++.h>
//此处省略快读快输，见我的主页
//它将这个程序优化了约 4ms 
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
using namespace std;
ll t,n,k,m; //意义如题面 
ll log2(ll x){//用不断除以 2 的方式求二进制长度（仅比转换成二进制少了取余，因此很明显正确） 
	ll ans=0;
	while(x){
		ans++;
		x/=2;
	}
	return ans;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>k>>m;
		if(log2(m)<log2(k)){//m 的二进制长度小于 k，无解 
			cout<<"-1\n";
		}
		else if(m<k){//m<k 的情况，见 Part2-2 
			if(n==1)cout<<"-1\n";//一项不够，无解 
			else{
				cout<<(1ll<<log2(k)-1)<<' '<<k-(1ll<<log2(k)-1);//左移，1<<k 结果为 2^k 
				for(int i=0;i<n-2;i++){//补 0 
					cout<<" 0";
				}
				cout<<endl;
			}
		}
		else{
			cout<<k;
			for(int i=0;i<n-1;i++){//补 0 
				cout<<" 0";
			}
			cout<<endl;
		}
	}
	return 0;
}