luogu#P11171. 「CMOI R1」mex1
「CMOI R1」mex1
题目背景
小 U 对于从一个集合映射到一个数的函数很感兴趣,而 是一个很好的例子。
指的是在集合 中没有出现过的最小非负整数。
题目描述
多组数据。
每组数据,给定 ,要求构造序列 满足
$$\sum\limits_{S\neq \emptyset,S\subseteq \{1,2,...,n\}}\text{mex}(a_{S_1},a_{S_2},...,a_{S_{|S|}})=c $$其中要求 。可以证明在该题的数据范围内如果存在解,则在 时一定存在解。
输入格式
第一行一个整数,数据组数 。
之后 行每行一个非负整数 。
输出格式
对于每组数据:
如果无解,则仅输出一行一个整数 。
否则,第一行输出一个正整数 。
第二行输出 个非负整数 。
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
提示
样例解释
我有一个绝妙的解释,可惜这里写不下。
数据范围
为 编号。
特殊性质 | 分数 | 特殊性质 | 分数 | ||
---|---|---|---|---|---|
对于 的数据,,。
提示
由于部分 STL 的常数较大,如果认为你的时间复杂度没有问题却 TLE,请不要使用 STL。
请注意输出效率,这里提供一种快写模板(请不要用以下代码输出负数):
void write(int x){
if(x>9)write(x/10);
putchar(x%10+'0');
}