luogu#P11171. 「CMOI R1」mex1

    ID: 15096 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>数学2024洛谷原创Special JudgeO2优化深度优先搜索,DFS剪枝构造

「CMOI R1」mex1

题目背景

小 U 对于从一个集合映射到一个数的函数很感兴趣,而 mex\text{mex} 是一个很好的例子。

mex(S)\text{mex}(S) 指的是在集合 SS 中没有出现过的最小非负整数。

题目描述

多组数据。

每组数据,给定 cc,要求构造序列 a1,a2,...,an[0,2×109]a_1,a_2,...,a_n\in [0,2\times 10^9] 满足

$$\sum\limits_{S\neq \emptyset,S\subseteq \{1,2,...,n\}}\text{mex}(a_{S_1},a_{S_2},...,a_{S_{|S|}})=c $$

其中要求 1n401\le n\le40。可以证明在该题的数据范围内如果存在解,则在 1n401\le n\le 40 时一定存在解。

输入格式

第一行一个整数,数据组数 TT

之后 TT 行每行一个非负整数 cc

输出格式

对于每组数据:

如果无解,则仅输出一行一个整数 1-1

否则,第一行输出一个正整数 nn

第二行输出 nn 个非负整数 a1,a2,...,ana_1,a_2,...,a_n

5
120
8128
248
0
5
7
1 9 1 9 8 1 0
13
1 1 4 5 1 4 1 9 1 9 8 1 0
8
1 2 3 9 0 7 3 8
7
1 2 3 9 7 3 8
-1

提示

样例解释

我有一个绝妙的解释,可惜这里写不下。

数据范围

ididsubtask\text{subtask} 编号。

idid 特殊性质 分数 idid 特殊性质 分数
11 c10c\le10 33 66 c1×106c\le1\times 10^6 1515
22 c30c\le30 66 77 T10T\le 10 55
33 c500c\le500 88 T5×104T\le 5\times 10^4 1515
44 c2×103c\le2\times 10^3 55 99 T8×104T\le 8\times 10^4 1010
55 c1×105c\le1\times 10^5 2020 1010 1515

对于 100%100\% 的数据,T105T\le 10^50c2×1090\le c\le 2\times 10^9

提示

由于部分 STL 的常数较大,如果认为你的时间复杂度没有问题却 TLE,请不要使用 STL。

请注意输出效率,这里提供一种快写模板(请不要用以下代码输出负数):

void write(int x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}