题意

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
勇太有n个[0,8192)中的整数，现在六花可以从中选出若干个数（不可以不取），她的方案需要满足她选出的所有数的异或和恰好等于它们AND（二进制与运算）起来的值，现在勇太想让六花求出满足条件的方案数。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
n≤50

题解

今天早上想到了，但是没有打出来
我们考虑到，如果暴力搞的话，明显是$2^{13}*2^{13}$的
这个复杂度是明显过不去的
然后我们发现了一点有用的东西，就是对于第i位，如果他是1的话，那么他一定是选的所有数这一位都是1
这个时候，我们只需要知道他选择的数是奇数还是偶数个就可以判断和法了
同样的，如果是0，那么我们要知道的是选择的1是奇数个还是偶数个
我们选择的数是奇数个还是偶数个是不需要状压进状态的
那么这样的话，就只有$2*3^{13}$种状态
可以通过
但是转移的话，如果一位一位做的话，就会多一个13的转移常数
考虑预处理
于是上网看了一下别人的写法，觉得还不错啊
我们考虑到，如果知道and的和的话，我们其实只需要知道他0的那些位抑或和哪些是1，再结合奇偶个数就可以得出抑或值了。
这个的话，枚举自己显然是可以$3^{13}$的
这样子就好些多了
先预处理出来所有状态，转移的时候看一看就可以做到O(1)转移了
几乎搬运了一份代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int NN = 1594323;
const int N=55;
int n;
int a[N];
int tot,Xor[NN],And[NN];
int id[8192][8192];
void prepare ()
{tot=0;for (int u=0;u<8192;u++){int i=((~u)&8191);for (int j=i;;j=(j-1)&i){And[tot]=u;Xor[tot]=j;id[u][j]=tot++;if (j==0) break;}}//printf("%d\n",tot);
}
LL f[2][NN][2];
int main()
{scanf("%d",&n);for (int u=1;u<=n;u++)  scanf("%d",&a[u]);prepare();int now=0;f[now][id[8191][0]][0]=1;
// printf("YES:%d\n",id[8191][0]);for (int u=1;u<=n;u++){for (int i=0;i<tot;i++){f[now^1][i][0]=f[now][i][0];f[now^1][i][1]=f[now][i][1];}for (int i=0;i<tot;i++){for (int j=0;j<=1;j++)//选了奇数个还是偶数个 {if (f[now][i][j]==0) continue;// printf("%d %d %d\n",now,i,j);int x=Xor[i],y=And[i];if (j==1) x|=y;x^=a[u];y&=a[u];x&=(~y);f[now^1][id[y][x]][j^1]+=f[now][i][j];}}now^=1;}LL ans=f[now][id[0][0]][0];for (int u=1;u<tot;u++)if (Xor[u]==0)ans=ans+f[now][u][1];printf("%lld\n",ans);return 0;
}