Codeforces Round 958 (Div. 2) 1988C题解

CF1988C Increasing Sequence with Fixed OR 题解

题目简述

给你一个正整数 $n(1 \leq 10^{18})$，让你构造一个序列 $a$ ，满足两个性质。

• $a_i | a_{i-1} = n$ （其中 $|$ 为按位或运算）
• $a_i > a_{i-1}$

思路

我们首先根据样例，从大到小列出一组数据的十进制和二进制

十进制	二进制
23	10111
22	10110
21	10101
18	10010
7	00111

这么一看，我们好像看不出一些明显的规律，我们再推一下，改变数字，使其合理的可能呢？（对于构造题，我们可以结果和样例不一样）

我们将其改为一下表示（$18$ 变成了 $19$）

十进制	二进制
23	10111
22	10110
21	10101
19	10011
7	00111

我们可以发现一个规律，修改后的表格中，除了 $22$ 和 $23$ 以外，他们均满足 $popcount(a_i \oplus a_{i-1}) = 2$（其中 $\oplus$ 为按位异或，在 C++ 中运算符号为 ^ 或 xor）

对于这个规律，我们推广到其他样例中（其他的再自己带入啦）

十进制	二进制	$\leftarrow$修改前，修改后$\rightarrow$	十进制	二进制
14	1110	无修改	14	1110
12	1100	无修改	12	1100
10	1010	无修改	10	1010
4	0100	$4 \to 6$	6	0110

最后发现除了第一个和第二个元素，其他元素都可以构造出一个这样的序列，满足

• $popcount(a_i \oplus a_{i-1}) = 2$

换句话来说，这个性质的体现是，两个相邻的数之间，存在两个位不相同。也就是说，针对这个性质，我们只需要知道了 $a_i$，我们就可以枚举出 $a_{i+1}$ 或 $a_{i-1}$。

而题目中要求该序列还需要满足 $a_i > a_{i-1}$，而我们的 $a$ 序列的最后一个数是已知的（$n$本身）。但是性质是在倒数第二个元素开始才体现。

对于我们表中的第一个和第二个元素，我们可以知道，第一个元素为 $n$ 本身。而第二个元素，是第一个元素翻转了 $lowbit$ 的结果，即 $n \oplus lowbit(n)$。

到此，我们便知道了倒数第二个元素，所以对于这个序列，我们可以从大到小枚举来构造。

需要注意的一点是，如果 $popcount(n) = 1$，即 $n$ 仅有一个位是 $1$，那么 $n$ 不可再分，构造的序列结果一定为 $[n]$。对于这个情况，记得特判。

代码如下

#ifdef _MSC_VER               // 如果编译器是 msvc
import std.compat;            // 导入标准模块（包含C++23的print库）
#else                         // 如果不是
#include <bits/stdc++.h>      // 导入万能头
template<typename... Args>    // 再手写一个简单的print库函数
void print(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
}
template<typename... Args>
void println(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
    std::cout.put('\n');
}
#endif
// 再拓展一下print库的功能，更好的替换掉 cout 风格打印
void println() { std::cout << '\n'; }
void print(const std::string_view s) { std::cout << s; }
void println(const std::string_view s) { std::cout << s << '\n'; }
using namespace std;
// 查找第一个小于 val 的 res，满足 popcount(val ^ res) == 2 和 val | res == n
uint64_t find(const auto &val, const uint64_t &n) {
    bitset<64> bits = val;              // 转成bitset，方便直接操作位
    for (int i = 0; i < 64; i++) {      // 从大到小枚举
        bits[i] = not bits[i];          // 反转第 i 位
        for (int j = i + 1; j < 64; j++) {
            bits[j] = not bits[j];      // 反转第 j 位
            auto tmp = bits.to_ullong();
            if (tmp < val and n == (tmp | val))
                return tmp;             // 若找到的值小于val，且满足条件，则为结果
            bits[j] = not bits[j];      // 反转第 j 位回去
        }
        bits[i] = not bits[i];          // 反转第 i 位回去
    }
    return -1;                          // 找不到返回 -1
}

void solve() {
    uint64_t n;                         // 无符号long long，方便操作位
    cin >> n;
    if (popcount(n) == 1) {             // 若这个数只有一个位，那么这个数只可分成自己
        println("1\n{}", n);   // 打印 1 换行 n
        return;
    }
    vector answer{n, n ^ n & -n};      // 初始化答案序列为 [n, n 翻转lowbit的值]
    for (auto res = find(answer.back(), n); res != -1; res = find(answer.back(), n))
        answer.emplace_back(res);      // 查找小于back()且符合条件的最大值，将其添加进答案
    println("{}", answer.size());// 打印答案长度
    for (auto &&i: answer | views::reverse)
        print("{} ", i);     // 反向遍历序列answer，并且打印元素
    println();                         // 记得换行
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int64_t t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}