CF1988C Increasing Sequence with Fixed OR 题解

题意简述

给定正整数 $n$，要求构造一个严格递增的整数序列 $a_1 < a_2 < \dots < a_k$，满足：

• $a_i \le n$；
• 对于所有 $2 \le i \le k$，有 $a_i \mid a_{i-1} = n$（按位或）。

求序列的最大长度 $k$，并输出任意一个最长序列。$n \le 10^{18}$，多组数据，序列总长度 $\le 5 \times 10^5$。

核心观察：按位或的约束

条件 $a_i \mid a_{i-1} = n$ 意味着：对于 $n$ 的二进制表示中每一个为 $1$ 的位，$a_i$ 和 $a_{i-1}$ 中至少有一个在该位上为 $1$；而对于 $n$ 中为 $0$ 的位，两者必须都为 $0$。

换言之，所有 $a_i$ 的二进制表示必须是 $n$ 的子集（即 $a_i \;\&\; \sim n = 0$），且相邻两项必须共同覆盖 $n$ 中所有的 $1$ 位。

构造最长序列

由于 $a_i$ 是 $n$ 的子集，且序列需严格递增，我们可以从高位到低位消去 $1$ 来依次生成前驱。

具体方法

1. 令最后一个元素 $a_k = n$（显然最大）。
2. 每次选取当前 $n$ 中最低位的一个 $1$，将它变为 $0$，得到一个新的数作为前一个元素。
3. 重复直至数字变为 $0$，结束。

例如 $n = 23 = (10111)_2$：

倒序输出即为：$[7, 19, 21, 22, 23]$。

为什么这样是最长的？

设 $n$ 的二进制中 $1$ 的个数为 $c$。每个 $a_i$ 都是 $n$ 的子集（即位 $1$ 的集合是 $n$ 中 $1$ 的子集）。

考虑序列的二进制包含关系：由于 $a_i < a_{i+1}$（严格递增），且 $a_{i+1} \mid a_i = n$，这意味着 $a_{i+1}$ 必须比 $a_i$ “多出”某些 $1$ 位（至少一个）。而所有 $1$ 位的总数只有 $c$ 个，因此序列长度不可能超过 $c$（包括 $n$ 本身）。

上述构造方法恰好每步消去一个 $1$，序列长度达到 $c$，故为最长。

Lowbit 实现

利用 lowbit(x) = x & -x 提取最低位的 $1$，循环消去即可。

时间复杂度：$O(T \log n)$，空间 $O(\log n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;

        vector<ll> ans = {n};
        for (ll m = n; m; ) {
            ll t = m & -m;          // lowbit
            m -= t;
            if (n - t > 0)
                ans.push_back(n - t);
        }

        // ans 中存储的是从大到小的顺序，需要逆序输出
        reverse(ans.begin(), ans.end());
        cout << ans.size() << '\n';
        for (ll x : ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}