题解：AT_arc138_d [ARC138D] 左方之地

· · 题解

我愿称为超神脑筋急转弯，准备扔给同学。

最近在补 /contest/55488 这一场的题，发现 ACE 全是神秘构造的时候就在想这场 div.2 怎么出成 arc 了，然后你告诉我这题被 AT 变成了 AT_arc138_d，绷不住了。

做一轮异或差分，容易发现每个位置都是 \text{popcount}(x)=k 的数。

考虑转而用这些数字构造差分数列，我们需要让每一个前缀的异或和互不相同。

众所周知，插进线性基的数字，任意取一个子集出来异或和都是不同的。

那么我们把符合条件的数字插进线性基，如果基满秩那么才可以生成所有数字，此时用格雷码枚举子集即可。

时间复杂度 O(2^nn)。

#include<bits/stdc++.h>
using namespace std;
const int MB=60;
int p[MB+5];
bool ins(int x){
    for(int i=MB;i>=0;i--)
    if((1ll<<i)&x){
        if(!p[i]){p[i]=x;return 1;}
        else x^=p[i];
    }
    return 0;
}
vector<int>ve;
int lst;
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<(1<<n);i++)
    if(__builtin_popcount(i)==k)
    if(ins(i))ve.push_back(i);
    if(ve.size()==n){
        cout<<"Yes\n";
        for(int i=0;i<(1<<n);i++){
            int x=i^(i>>1);
            int flc=0;
            for(int j=0;j<n;j++)
            if((x>>j)&1)flc^=ve[j];
            cout<<flc<<' ';
        }
    }else
    cout<<"No";
    return 0;
}
// 所以，比起算式，比起魔术式，莫妮卡现在更想要回忆。
// 就像那满抽屉珍藏的宝物一般，闪闪发亮的回忆。