CF-1174D

Ehab and the Expected XOR Problem

题意

给 $n(1\le n\le 18),x(1\le x<2^{18})$ , 构造一个数组 $a(1\le a_i<2^n)$ , 使得这个数组的任意子段的异或和不为 0 或 $x$

题解

要使得这个数组的任意子段的异或和不为 0, 只需要保证数组的前缀和都不同就可以了. 假设 $A\text^B=x$ , 可以将 $[0,2^n-1]$ 分为两部分, 没部分里面的数两两异或都不为 $x$

代码

bool vis[N];
vii v;
int main() {
    int n,x;
    in(n,x);
    int p=(1<<n);
    if(x>=p){
        outln(p-1);
        for1(i,p-1){
            out(i^(i-1));
        }
    }else{
        p-=2;
        outln(p/2);
        v.pu_b(0);
        vis[x]=1;
        for1(i,p+1){
            if(vis[i]==0){
                v.pu_b(i);
                vis[i]=vis[i^x]=1;
            }
        }
        for1(i,(int)v.size()-1){
            out(v[i]^v[i-1]);
        }
    }
    return 0;
}