AT_abc269_c [ABC269C] Submask

题目描述

给定一个非负整数 $N$，请按升序输出所有满足以下条件的非负整数 $x$：

• 将 $x$ 用二进制表示时，其所有为 $1$ 的位的集合，必须是 $N$ 的二进制表示中为 $1$ 的位的集合的子集。
  • 换句话说，对于所有非负整数 $k$，如果 $x$ 的 $2^k$ 位为 $1$，那么 $N$ 的 $2^k$ 位也必须为 $1$。

输入格式

输入以以下格式从标准输入读入。

$N$

输出格式

请将所有满足条件的非负整数 $x$ 按升序，每行输出一个十进制整数。

输入输出样例 #1

输入 #1

11

输出 #1

0
1
2
3
8
9
10
11

输入输出样例 #2

输入 #2

0

输出 #2

0

输入输出样例 #3

输入 #3

576461302059761664

输出 #3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

说明/提示

限制

• $N$ 是整数。
• $0 \leq N < 2^{60}$。
• $N$ 的二进制表示中为 $1$ 的位不超过 $15$ 个。

样例解释 1

将 $N=11_{(10)}$ 用二进制表示为 $1011_{(2)}$。满足条件的非负整数 $x$ 如下：

• $0000_{(2)}=0_{(10)}$
• $0001_{(2)}=1_{(10)}$
• $0010_{(2)}=2_{(10)}$
• $0011_{(2)}=3_{(10)}$
• $1000_{(2)}=8_{(10)}$
• $1001_{(2)}=9_{(10)}$
• $1010_{(2)}=10_{(10)}$
• $1011_{(2)}=11_{(10)}$

样例解释 3

输入可能超出 $32$ 位有符号整数的范围。

由 ChatGPT 4.1 翻译