CF1174D Ehab and the Expected XOR Problem(二进制)

做法

求出答案序列的异或前缀和(sum_i)，([l,r])子段异或和可表示为(sum_rigoplus sum_{l-1})

故转换问题为，填(sum)数组，数组内的元素不为(0)且互不相同，且两两异或不为(x)

预处理(x)为多对值，每对值异或起来为(x)，显然是两两互不影响的，每对值选择任意一个填就行了

最后还得从(sum_i=igoplus_{j=1}^i a_i)转换为(a_i)

code

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=2e6+9;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }return x*f;
}
LL n,x,tot,sum;
LL to[maxn],visit[maxn],ans[maxn];
vector<LL> e;
int main(){
	n=Read(); x=Read();
	LL up(1<<n);
	e.push_back(0);
	visit[x]=1;
	for(LL i=1;i<up;++i){
		if(visit[i]) continue;
	    visit[x^i]=1;
		e.push_back(i);
	}
	printf("%d
",e.size()-1);
	for(LL i=1;i<e.size();++i) printf("%d ",e[i]^e[i-1]);
	return 0;
}