#P15716. 零和收藏盒

    ID: 14928 传统题 2000ms 512MiB 尝试: 4 已通过: 1 难度: 7 上传者: 标签>算法基础构造动态规划背包DP贪心CF2300

零和收藏盒

题目描述

工匠 Kira 正在制作一只“零和收藏盒”。盒子里会放入若干个整数,每次游客可以从这些整数中任选一些,组成一个子集。Kira 希望这只盒子刚好有 KK 种选择方式,使得所选整数之和为 00。

形式化地,你需要构造一个数组

A1,A2,…,ANA_1,A_2,\ldots,A_N

满足以下条件:

  • 1≤N≤301\le N\le 30;
  • 对所有 ii,有 −1016≤Ai≤1016-10^{16}\le A_i\le 10^{16};
  • 在集合 {1,2,…,N}\{1,2,\ldots,N\} 的所有子集 SS 中,恰好有 KK 个子集满足
∑i∈SAi=0.\sum_{i\in S} A_i=0.

空集也算作一个子集。

可以证明,在本题限制下总能构造出合法数组。

输入格式

第一行包含一个整数 tt,表示测试用例数量。

接下来 tt 行,每行包含一个整数 KK。

输出格式

对每个测试用例,输出两行。

第一行输出一个整数 NN,表示构造数组的长度。

第二行输出 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

如果存在多种合法构造,输出任意一种即可。

数据范围

  • 1≤t≤10001\le t\le 1000;
  • 1≤K≤1061\le K\le 10^6;
  • 1≤N≤301\le N\le 30;
  • −1016≤Ai≤1016-10^{16}\le A_i\le 10^{16}。

样例 1

输入

2
3
16

输出

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

样例说明

数组元素不要求互不相同。样例输出只是可行构造之一。