CF2180C

赛场上没想出最后一个点，没做出来www

给定一个数 $x$，求一个序列，他们的异或和等于 $x$，并且每个数不大于 $x$，求使得序列和最大的序列。

• 从高位往低位考虑：

因为让一个高位填 1 所带来的贡献比让所有低位填 1 带来的贡献都要大。

根据异或的性质，假设当前是第 $i$ 位，如果是 1，那么当前这位是 1 的数的个数必须是奇数。

序列大小为 $k$，如果 $k$ 是奇数，那么这位都可以填 1；反之，就有一个数这一位必须填 0。

如果第 $i$ 位是 0，那么当前这位 1 的个数必须是偶数。

但是这里需要考虑了，因为每个数都不能超过 $x$，所以如果之前填的前缀和 $x$ 一样的话，那么这一位无论如何都不能填 1 了（类比数位 DP 中的 limit 概念）

那么什么情况下才可以填 1 呢？limit 为 false 的情况，所以我们可以维护两个集合，一个是有限制的 T，一个是没有限制的 L。

初始时所有元素均有限制。

当第 $i$ 位是 1 且序列大小为偶数时，此时必须有一个数这一位要填 0，那么选 T 集合中的数一定更优，这样这个数便从 T 集合转移到了 L 中。

当第 $i$ 位是 0 时，T 集合中所有数都必须填 0，考虑 L 集合，如何 L 集合大小是偶数，那么就都可以填 1，反之，就需要有一个数填 0，这个 0 给谁都可以，因为不会产生任何影响。

参考代码：

代码中前缀代表 T 集合，后缀代表 L 集合，仅维护 L 集合长度。

注意如果所有数都在 L 集合中了的话，就不需要再新加了。

#include <bits/stdc++.h>
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;

void solve() {
  int n, k;
  cin >> n >> k;
  int len = 30;
  while ((n >> len) == 0)
    len--;
  len++;
  vi ans(k + 1);
  int L = 0;
  for (int i = len - 1; i >= 0; i--) {
    int digit = (n >> i) & 1;
    if (digit == 1) {
      if (k & 1) {
        for (int j = 1; j <= k; j++) {
          ans[j] += (1 << i);
        }
      } else {
        for (int j = 1; j <= k; j++) {
          ans[j] += (1 << i);
        }
        ans[max(k - L, 1)] -= (1 << i);
        L++;
        L = min(k, L);
      }
    } else {
      if (L & 1) {
        for (int j = k - L + 2; j <= k; j++)
          ans[j] += (1 << i);
      } else {
        for (int j = k - L + 1; j <= k; j++)
          ans[j] += (1 << i);
      }
    }
  }
  for (int i = 1; i <= k; i++)
    cout << ans[i] << ' ';
  cout << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}