102692: [AtCoder]ABC269 C - Submask
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $300$ points
Problem Statement
You are given a non-negative integer $N$. Print all non-negative integers $x$ that satisfy the following condition in ascending order.
- The set of the digit positions containing $1$ in the binary representation of $x$ is a subset of the set of the digit positions containing $1$ in the binary representation of $N$.
- That is, the following holds for every non-negative integer $k$: if the digit in the "$2^k$s" place of $x$ is $1$, the digit in the $2^k$s place of $N$ is $1$.
Constraints
- $N$ is an integer.
- $0 \le N < 2^{60}$
- In the binary representation of $N$, at most $15$ digit positions contain $1$.
Input
The input is given from Standard Input in the following format:
$N$
Output
Print the answer as decimal integers in ascending order, each in its own line.
Sample Input 1
11
Sample Output 1
0 1 2 3 8 9 10 11
The binary representation of $N = 11_{(10)}$ is $1011_{(2)}$.
The non-negative integers $x$ that satisfy the condition are:
- $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)}$
Sample Input 2
0
Sample Output 2
0
Sample Input 3
576461302059761664
Sample Output 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
The input may not fit into a $32$-bit signed integer.
Input
题意翻译
给定一个非负整数 $n$,按升序打印满足下列条件的所有非负整数 $x$。 对于每一个非负整数 $k$ 都成立: 如果二进制下的 $x$ 的 $k$ 位上的数字是 $1$,则二进制下的 $n$ 的 $k$ 位上的数字也是 $1$。Output
得分:300分
问题描述
给你一个非负整数 $N$。按升序顺序输出所有满足以下条件的非负整数 $x$。
- 二进制表示中,$x$ 的含有 1 的数位是 $N$ 的含有 1 的数位的子集。即对于每一个非负整数 $k$,如果 $x$ 的 "$2^k$ 位" 是 1,那么 $N$ 的 "$2^k$ 位" 也是 1。
限制条件
- $N$ 是一个整数。
- $0 \le N < 2^{60}$
- $N$ 的二进制表示中,最多有 $15$ 个数位含有 1。
输入
输入通过标准输入给出,格式如下:
$N$
输出
按升序顺序输出答案,每个答案占一行。
样例输入 1
11
样例输出 1
0 1 2 3 8 9 10 11
$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)}$
样例输入 2
0
样例输出 2
0
样例输入 3
576461302059761664
样例输出 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
输入可能无法容纳在 $32$ 位有符号整数中。