思路与证明

关键变换

设 $x$ 的二进制在 $20$ 位内，令集合 $S$ 为 $x$ 中为 $1$ 的位位置集合，$C$ 为其补集（即 $x$ 中为 $0$ 的位，数量记为 $m$）。 对任意候选数 $a$，要让与任意另一个 $a'$ 有 $a$ & $a'$=$x$，显然 $a$ 在 $S$ 上必须全为 $1$。于是可以写成

题目内容

小美有一个最喜欢的小于 $2^{20}$ 的非负整数 $x$ 。

我们称数组 $a$ 是 美丽的 ，当且仅当其满是以下所有条件：

• 数组 $a$ 中的每个元素都小于 $2^{20}$ 。

• 数组 $a$ 中 不包含 相同的数。

• 对于数组 $a$ 中任意两个处在不同位置的数 $a_i$ 和 $a_j$ ，都满足 $a_i$ & $a_j =x$，其中 & 为按位与运算。特别地，当数组长度为 $1$ 时，也视为满足此条件。

现在小美想让你帮他找到一个最长的美丽数组。如果存在多个最长的美丽数组，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

输入描述

每个测试文件均包含多组测试数据。一行输入一个整数 $T(1≤T≤500)$ 代表数据组数，每组测试数据描述如下：

输入一行一个整数 $x(0≤x<2^{20})$ ，表示小美最喜欢的非负整数。

输出描述

对于每组测试数据，先输出一行一个整数 $k(1≦k≦100)$，表示最长的美丽数组的长度。可以证明在本题的数据范围内，最长的美丽数组的长度不会超过 $100$ 。

接下来，在第二行输出 $k$ 个不同整数 $a_1,a_2,…,a_k(0≦a_i< 2^{20})$ ，表示你找到的最长美丽数组。

样例1

输入

2
1048575
1048573

输出

1
113514
2
1048573 1048575

说明

对于第二组测试数据，找到的最长美丽数组 $a$ 为 {$1048573,1048575$} 。检查发现， $1048573<2^{20}，1048575<2^{20}$ ，且 $1048573$ & $1048575=1048573$ 。可以证明，不存在长度大于 $2$ 的美丽数组。