CF D. Ehab and the Expected XOR Problem 贪心+位运算

题中只有两个条件：任意区间异或值不等于0或m. 

如果只考虑区间异或值不等于 0，则任意两个前缀异或值不能相等. 

而除了不能相等之外，还需保证不能出现任意两个前缀异或值不等于m. 

即 $xor[i]$^$xor[j]!=m$, $Rightarrow$ m^xor[j] 这个异或前缀就不可以再次出现了.     

用一个数组标记一下就好了~

#include <bits/stdc++.h>          
#define N 1000000    
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int vis[N],b[N];           
void solve() 
{
    int n,m,i,j,cur=1,cnt=0;   
    memset(vis,0,sizeof(vis));   
    scanf("%d%d",&n,&m);   
    vis[m]=1;                  
    for(i=1;i<=(1<<n);++i) 
    {      
        while(vis[cur]) ++cur;        
        if((cur^b[cnt-1]) >= (1<<n)) break;                                                   
        b[++cnt]=cur;          
        vis[cur^m]=1;     
        ++cur;                                            
    }
    printf("%d
",cnt);     
    for(i=0;i<cnt;++i) printf("%d ",b[i]^b[i+1]);          
}
int main() 
{  
    int i,j,T; 
    // setIO("input");         
    solve();       
    return 0; 
}