CF1988C Increasing Sequence with Fixed OR Solution

题意简述如下：

给定一个正整数 \(n\)，请构造一个正整数序列使其满足以下条件并尽可能长：这个序列中每个数都大于等于 \(1\) 且小于等于\(n\)；这个序列是单调递增的；这个序列中任意两个相邻的数按位或的结果都为 \(n\)。

通过手玩或者写个最长上升子序列可以发现，我们记这个数在二进制位上 \(1\) 的个数为 \(c\)，当 \(c=1\) 时，序列最长的长度为 \(1\)，否则为 \(c+1\)。

然后很显然的构造，当 \(c=1\) 时直接输出自身，否则这 \(c+1\) 个数中第 \(i\) 个数为将 \(n\) 从高位到低位第 \(i\) 个 \(1\) 改为 \(0\) 后的值，当然第 \(c+1\) 个数一定最大，就是 \(n\)。

最后为什么长度为 \(c+1\) 时是最大的，可以感性理解一下，显然上文中的构造方法是每一个数都是 \(n\) 的二进制下去掉一位，如果去掉的位数大于一位，又要保证其单调递增，那么长度就会小于 \(c+1\)。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
LL t[100], tot = 0;
 
int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	LL T, n; cin >> T;
	while (T --) {
		cin >> n; tot = 0;
		for (LL i = 0; i <= 62; i ++) {
			if ((n >> i) & 1) t[++ tot] = i;
		}
		if (tot == 1) {
			cout << "1\n" << n << "\n";
			continue;
		} else cout << tot + 1 << "\n";
		for (LL i = tot; i >= 1; i --) {
			cout << (n ^ (1LL << t[i])) << " ";
		}
		cout << n << "\n";
	}
	return 0;
}