AT_jsc2022_final_d And is 0
题目描述
给定一个整数 $N$。
请你判断是否存在一个非负整数序列 $A=(A_1,A_2,\cdots,A_k)$，满足以下条件：
- $A$ 的长度 $k$ 满足 $1\leq k\leq 100$。
- $A$ 的每个元素都是满足 $0\leq A_i \leq 2^{20}-1$ 的整数。
- 设 $A$ 的所有非空（不要求连续）子序列中，元素按位与（bitwise AND）结果为 $0$ 的子序列数量恰好为 $N$ 个。这里，不同位置选出的子序列即使值相同，也视为不同。
按位与 $\mathrm{AND}$ 运算定义如下：
对于整数 $A,B$，其按位与 $A\ \mathrm{AND}\ B$ 的二进制第 $2^k$ 位，等于 $A$ 和 $B$ 的该位都为 $1$ 时为 $1$，否则为 $0$。
例如，$3\ \mathrm{AND}\ 5=1$，因为 $011\ \mathrm{AND}\ 101 = 001$。
更一般地，$k$ 个整数 $p_1,p_2,\ldots,p_k$ 的按位与为
$$(\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k)$$
并且可以证明其值与顺序无关。
输入格式
输入为一行：
> $N$
输出格式
如果不存在满足条件的数列 $A$，请输出 `-1`。
如果存在，请输出如下格式：
> $k\ A_1\ A_2\ \cdots\ A_k$
如果有多组答案，输出任意一组均视为正确。
说明/提示
### 样例解释 1
使 $A$ 的非空子序列中，按位与为 $0$ 的有 $3$ 个，如下：
- $(2,1)$（取第 $1$、$2$ 个元素）
- $(2,1)$（取第 $1$、$3$ 个元素）
- $(2,1,1)$（取第 $1$、$2$、$3$ 个元素）
### 数据范围
- $1\leq N\leq 2\times 10^5$
- 输入的值均为整数。
由 ChatGPT 5 翻译