考试的时候理解错题了（无语）……
那个看似很长的式子的意义其实是逻辑左移动，就是最高位会出现在最低位的意思（这谁能看出来……）。此时x取值经过那个式子后仍然可以遍历[0,2^n),
O（m）枚举断点，那么x会异或[1,i],逻辑左移后异或[i+1,m],将这个数加入01trie即可，如果一个节点有两个儿子，那么对手一定可以把这一位弄成0，反之你一定可以把这位弄成1，在trie树上深搜即可。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<bitset> 5 #define LL long long 6 #define int LL 7 #define MAXN 100010 8 using namespace std; 9 int n,m; 10 LL a[MAXN],sum[MAXN],al,ca; 11 struct Trie 12 { 13 int ch[MAXN*30][2],tot,tem[33],cnt; 14 void clear(){memset(ch,0,sizeof(ch));tot=1;} 15 void insert(int x) 16 { 17 int now=1; 18 for(int i=1;i<=n;i++){tem[i]=((x>>(n-i))&1);} 19 for(int i=1;i<=n;i++) 20 { 21 if(!ch[now][tem[i]])ch[now][tem[i]]=++tot; 22 now=ch[now][tem[i]]; 23 } 24 } 25 void dfs(int root,int w,LL ans) 26 { 27 if(w<0) 28 { 29 if(ans==al)ca++; 30 if(ans>al)al=ans,ca=1; 31 return; 32 } 33 if(ch[root][0]&&ch[root][1]) 34 dfs(ch[root][0],w-1,ans), 35 dfs(ch[root][1],w-1,ans); 36 else if(ch[root][0]) 37 dfs(ch[root][0],w-1,ans^(1<<w)); 38 else if(ch[root][1]) 39 dfs(ch[root][1],w-1,ans^(1<<w)); 40 } 41 }trie; 42 signed main() 43 { 44 trie.clear(); 45 cin>>n>>m;LL bin=(1<<n),ooo=0; 46 for(int i=1;i<=m;i++)cin>>a[i]; 47 for(int i=m;i;i--)sum[i]=sum[i+1]^a[i]; 48 for(int i=0;i<=m;i++) 49 { 50 ooo^=a[i]; 51 LL tem=(2*ooo/bin+2*ooo)%bin;tem^=sum[i+1]; 52 trie.insert(tem); 53 } 54 trie.dfs(1,n-1,0); 55 cout<<al<<endl<<ca; 56 }