我们设pos[i]表示所有异或和为i的合法子序列中结尾数的最小值，这样可以判断序列是否递增。ans[i]=1/0表示有(1)或没有(0)异或和为i的合法子序列。
主要代码：
for(int i=1;i<=n;i++){
scanf("%d",&x);
for(int j=1;j<=512;j++){
if(ans[j]&&pos[j]<x){//如果有异或和为j的合法子序列并且将x加到最小值的后面还是一个递增子序列。
ans[j^x]=1;//有了结尾为j^x的递增子序列。
pos[j^x]=min(x,pos[j^x]);//结尾数可以是原先的也可以是新的x。
}
}
ans[x]=true;//有了结尾为x的递增子序列。
pos[x]=min(pos[x],x);//结尾数可以是原先的也可以是新的x。
}
统计答案的时候注意空序列也就是答案为0的也是合法的：
for(int i=1;i<=512;i++){
if(ans[i]) res++;
}
printf("%d\\n",res+1);
printf("0 ");
for(int i=1;i<=512;i++){
if(ans[i]) printf("%d ",i);
}
代码(求赞)：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool ans[N];
int n,x,res=0,pos[N];//pos[i]表示所有异或和为i的合法子序列中结尾数的最小值，这样可以判断序列是否递增。
int main(){
memset(ans,0,sizeof ans);
memset(pos,0x3f,sizeof pos);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
for(int j=1;j<=512;j++){
if(ans[j]&&pos[j]<x){//如果有异或和为j的合法子序列并且将x加到最小值的后面还是一个递增子序列。
ans[j^x]=1;//有了结尾为j^x的递增子序列。
pos[j^x]=min(x,pos[j^x]);//结尾数可以是原先的也可以是新的x。
}
}
ans[x]=true;//有了结尾为x的递增子序列。
pos[x]=min(pos[x],x);//结尾数可以是原先的也可以是新的x。
}
for(int i=1;i<=512;i++){
if(ans[i]) res++;
}
printf("%d\\n",res+1);
printf("0 ");
for(int i=1;i<=512;i++){
if(ans[i]) printf("%d ",i);
}
return ~(-1);
}
