题解说明

问题背景：
给定一个整数 $n$，我们希望从 $[1,n]$ 中选出若干个数，使得这些数的二进制 $1$ 的总数恰好等于 $n$。程序通过前缀和与贪心倒序遍历来构造解。

核心思路：
$1.$ 前缀和数组 $s[i]$：

• 定义 $s[i] = \sum_{j=1}^{i} \text{popcount}(j)$，即 $1 \sim i$ 的所有数的二进制 $1$ 的总和。
• 使用内置函数 $\_\_builtin\_popcount(i)$ 快速计算每个数的 $1$ 的个数。
• 这样 $s[i]$ 单调递增。

$2.$ 贪心倒序选择：

• 从 $i=n$ 倒序到 $1$，判断是否可以选择 $i$。
• 条件：若 $s[i-1] < n$，说明若不选 $i$，剩余的 $1$ 的数量不足以覆盖当前目标 $n$，因此必须选择 $i$。
• 选择 $i$ 后，将 $n \leftarrow n - \text{popcount}(i)$，并把 $i$ 加入结果集合。
• 这样保证每次选择都是必要的，最终得到一组满足条件的数。

$3.$ 输出：

• 输出结果集合的大小（选了多少个数）。
• 输出集合中的所有元素。

复杂度分析：

• 预处理前缀和 $O(n)$。
• 倒序遍历 $O(n)$。
• 总体复杂度 $O(n)$，适合 $n \leq 2 \times 10^6$。

#include <bits/stdc++.h>
// 正向循环宏：i从a到b（含a、b），register修饰提升循环效率
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
// 反向循环宏：i从a到b（含a、b）
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long  // 注释掉的长整型定义，按需开启

using namespace std;

/**
 * 快速读入整数函数
 * 功能：高效读取正负整数，处理非数字字符，适配大规模输入
 * 返回值：读取到的整数（含符号）
 */
inline int read() {
    char c = getchar();  // 读取一个字符
    int x = 0;           // 存储读取结果
    bool f = 0;          // 标记是否为负数（初始为非负）

    // 跳过非数字字符，同时判断负号（ASCII 45是'-'）
    for (; !isdigit(c); c = getchar())
        f ^= !(c ^ 45);  // c是'-'时，f取反（0→1，标记负数）

    // 读取数字字符，转换为整数（x<<1 + x<<3 等价于 x*10，位运算效率更高）
    for (; isdigit(c); c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);  // c^48 等价于 c-'0'，转字符为数字

    // 若为负数，返回-x；否则返回x
    if (f)
        x = -x;

    return x;
}

// 简化pair<int,int>的调用（fi=first，se=second）
#define fi first
#define se second
// 向vector尾部添加元素的宏
#define pb push_back
// 快速创建pair<int,int>的宏
#define mkp make_pair
typedef pair<int, int>pii;  // 定义pii为int型键值对
typedef vector<int>vi;       // 定义vi为int型向量

const int maxn = 2000005;  // 数组最大长度（适配n的最大可能值）
const int inf = 0x3f3f3f3f; // 定义无穷大（int型，用于边界判断）

int n;              // 输入的目标数值
int s[maxn];        // 前缀和数组：s[i] = 1~i每个数的二进制1的个数之和

signed main() {
    n = read();  // 读取目标数值n

    // 计算前缀和数组s：s[i]是1到i的二进制1的个数总和
    // __builtin_popcount(i)：内置函数，返回i的二进制表示中1的个数
    For(i, 1, n)s[i] = s[i - 1] + __builtin_popcount(i);

    vi res;  // 存储结果的向量（最终要输出的数字集合）

    // 从n倒序遍历到1，筛选符合条件的数字加入res
    Rep(i, n, 1) {
        // 条件：1~i-1的二进制1的个数总和 < 当前剩余的n
        if (s[i - 1] < n) {
            n -= __builtin_popcount(i);  // 剩余n减去i的二进制1的个数
            res.pb(i);                   // 将i加入结果集合
        }
    }

    // 输出结果集合的大小（元素个数）
    cout << res.size() << "\n";

    // 遍历输出结果集合中的每个元素
    for (int x : res)
        cout << x << " ";

    return 0;
}