#P16069. [2022国家队训练南京站]零和

    ID: 15280 传统题 2000ms 512MiB 尝试: 4 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-序列构造0/1 背包计数 DP倒序更新避免重复使用完全背包路径恢复

[2022国家队训练南京站]零和

题目描述

给定 KK,你需要构造一个长度为 nn 的序列 (Ai)i=1n(A_i)_{i=1}^n,满足:

  1. AiA_i 是 [−1016,1016][-10^{16},10^{16}] 之间的整数;

  2. 恰有 KK 个 {1,2,⋯ ,n}\{1,2,\cdots,n\} 的子集 SS 满足

    ∑i∈SAi=0\sum_{i\in S}A_i=0

    其中包含空集;

  3. nn 是 00 到 3030 之间的整数。

输入格式

本题多组测试。

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行一个整数 KK,表示查询参数。

输出格式

对于每组数据,输出两行:

第一行一个整数 nn,表示序列长度;

第二行输出 nn 个整数,表示构造出的序列。

样例一

输入

2
3
16

输出

5
2021 -1000 -1021 -2000 -21
4
0 0 0 0

数据范围与提示

子任务编号 K≤K\le 分值
1 10 15
2 100
3 2000
4 10000
5 100000
6 1000000 25

对于所有数据,满足:

1≤T≤1000,1≤K≤106.1\le T\le 1000, \qquad 1\le K\le 10^6.

图片

本题题面无图片。