[Aya Round 1 C] 文文的构造游戏

题目背景

众所周知，射命丸文和琪露诺是好朋友。但是文是大妖怪，非常聪明，而琪露诺是个笨蛋。为了提升琪露诺的智商，文便给琪露诺出了一道简单的题目。

题目描述

对于一个长度为 $l$ 的数列 $p$，定义 $S(p)$ 为所有元素的异或和，其中 $\oplus$ 指按位异或运算。

给定整数 $s,m$，判断能否构造一个长度为 $n$（$n$ 值自定）的数列 $a$，满足：

• $1\le n\le m$。
• $1\le a_i\le s$。
• $S(a)=0$。
• $a_1+a_2+\cdots +a_n=s$。

试构造任意一组合法解或报告无解。

输入格式

本题包含多组数据。

• 第一行输入一个整数 $T$，表示数据组数。
• 接下来 $T$ 行，每行输入两个整数 $s,m$。表示一组询问。

输出格式

• 输出共 $T$ 行。
• 对于每组数据：
  • 若有解，首先输出一个整数 $n$，然后输出 $n$ 个整数，表示 $a$。
  • 若无解，仅输出一行一个整数 $-1$。

样例 #1

样例输入 #1

2
14 9
3 3

样例输出 #1

3 3 5 6
-1

提示

样例解释

• 对于数据 $1$，容易发现 $3\oplus 5\oplus 6=0$，$3+5+6=14$。符合要求。
• 对于数据 $2$，发现数列 { 3 } , { 1 , 2 } , { 1 , 1 , 1 } \{3\},\{1,2\},\{1,1,1\} {3},{1,2},{1,1,1} 均不符合要求，故无解。

数据范围与约定

对于 $100\%$ 的数据，有 $1\le s\le 10^{18}$，$1\le m$，$1\le \sum m\le 10^6$。

友情提示，您可能需要使用较快的 I/O 方式。

思路

本题是思维题。

观察题目可知当 $m==1$ 时一定无解（ $S(a)\ne 0$ ）。

因为 $S(a)=0$ ，所以在二进制下每一位的 $1$ 的出现次数一定是偶数。

因为 $a_1+a_2+a_3+a_4+...+a_n=s$ ，使我们对本题的解法无法确定。

重新观察题目，发现题目有 $0\le n\le m$ 的保证，所以我们可以使 $n$ 尽量小，比如使 $n=2$ （因为 $n$ 为 $1$ 时 $S(a)\ne 0$ ）。

手写几组数据可以发现当 $s$ 为奇数无解，为偶数有解。

当 $s=01011101\cdots 01$ 时，若最后一位出现的次数为偶数则 $a_1+a_2+a_3+a_4+...+a_n\ne s$ ，若最后一位出现的次数为奇数则 $S(a)\ne 0$ 。因此 $s$ 为奇数就无解。
若 $s$ 为偶数，则可以使 $n=2\text{ , }{a}_1=a_2=\frac{s}{2}$ ，此时二进制下每一位的 $1$ 的出现次数为 $0$ 或 $2$ 。既满足 $S(a)=0$ ，又满足 $a_1+a_2=s$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;
namespace Solve
{
	#define int long long
	inline int read()
	{
		int x=0,f=1;
		char ch=getchar();
		while(!isdigit(ch))
		{
			if(ch=='-')f=-f;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			x=(x<<3)+(x<<1)+ch-'0';
			ch=getchar();
		}
		return x*f;
	}
	inline void write(int x)
	{
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
	int T,s,m;
	void work()
	{
		T=read();
		while(T--)
		{
			s=read();m=read();
			if(s%2==1||m==1)write(-1);
			else
			{
				write(2);
				putchar(' ');
				write(s>>1);
				putchar(' ');
				write(s>>1);
			}
			putchar('\n');
		}
	}
}
signed main()
{
	Solve::work();
}