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

    ID: 7568 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>数学洛谷原创Special JudgeO2优化构造洛谷月赛

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

题目背景

Problem Number: 23\textit{23}

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

题目描述

对于一个长度为 ll 的数列 pp,定义 S(p)S(p) 为所有元素的异或和,其中 \oplus按位异或运算

给定整数 s,ms,m,判断能否构造一个长度为 nnnn 值自定)的数列 aa,满足:

  • 1nm1 \le n \le m
  • 1ais1 \le a_i \le s
  • S(a)=0S(a)=0
  • a1+a2++an=sa_1+a_2+\cdots+a_n=s

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

输入格式

本题包含多组数据。

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

输出格式

  • 输出共 TT 行。
  • 对于每组数据:
    • 若有解,首先输出一个整数 nn,然后输出 nn 个整数,表示 aa
    • 若无解,仅输出一行一个整数 1-1
2
14 9
3 3
3 3 5 6
-1

提示

样例解释

  • 对于数据 11,容易发现 356=03\oplus5\oplus6=03+5+6=143+5+6=14。符合要求。
  • 对于数据 22,发现数列 {3},{1,2},{1,1,1}\{3\},\{1,2\},\{1,1,1\} 均不符合要求,故无解。

数据范围与约定

对于 100%100\% 的数据,有 1s10181\le s\le 10^{18}1m1 \le m1m1061 \le \sum m \le 10^6

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