[ARC138D] Differ by K bits 题解

小清新构造题。

首先 \(K=1\) 的情况是 trival 的，直接格雷码即可。

对于 \(K>1\)，我们发现题目的约束相当于 \(\operatorname{popcount}(P_i\oplus P_{(i+1)\bmod 2^N})=K\)，考虑 \(P_i\) 的差分序列 \(D_i\)，那么 \(D_i\) 一定是一个恰好有 \(K\) 位 \(1\) 的二进制数，记 \(S=\{i\mid 0\le i\le 2^N-1\land \operatorname{popcount}(i)=K\}\)，则 \(D_i\in S\)。

题目要求 \(P_i\) 不能重复，所以我们得到的 \(\bigoplus\limits_{j=0}^i D_j\) 必须不重，因此考虑先用线性基处理掉 \(S\) 中能被别的数表示出来的数，那么剩下的数可以保证：只要选数的方案不同，结果就不同。

于是我们只需要让每次选数方案的变化量为 \(1\) 即可，直接格雷码即可。

#include <iostream>
#include <vector>

using namespace std;

const int kN = 18;

int n, k, p[kN];
vector<int> l;

void A(int v) {
  int _v = v;
  for (int i = n - 1; i >= 0; --i) {
    if (v >> i & 1) {
      if (p[i]) {
        v ^= p[i];
      } else {
        p[i] = v, l.push_back(_v);
        break;
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < (1 << n); ++i) {
    int c = 0;
    for (int j = 0; j < n; ++j) {
      c += i >> j & 1;
    }
    if (c == k) {
      A(i);
    }
  }
  if (l.size() < n) {
    cout << "No";
    return 0;
  }
  cout << "Yes\n";
  for (int i = 0; i < (1 << n); ++i) {
    int p = i ^ (i >> 1), v = 0;
    for (int j = 0; j < n; ++j) {
      if (p >> j & 1) {
        v ^= l[j];
      }
    }
    cout << v << ' ';
  }
  return 0;
}