这是这场比赛上最简单的那道题,可惜我不会做

$0pts$

时间复杂度为$O(2^n)$的爆搜。


(借鉴了dnvtmf的题解)

不能打的DP

$dp[i][x][y]$表示前$i$个数中从中选出一些数,它们的异或和为$x$,位与和为$y$的方案数。
明显的,有$dp[i][x^a[i]][y^a[i]]+=dp[i-1][x][y],dp[i][x][y]+=dp[i-1][x][y].$
将初始化设为$dp[0][0][8191]=1$才能保证正确性。
但是,空间和时间均为$O(n*8191^2)$,双双爆炸。

STD

因为状态数太多了,所以减少状态。
考虑当取个数为奇数时,$x\&y=y$(考虑取的数每一位中有奇数个1或偶数个1的情况,加以推导可以得出结论)
偶数时,$x\&y=0$(参上)
因此可以建立起一个三元组$(xx,y,odd)$,其中$xx$表示$x\& (~y)$,实际意义为$x$有$1$的位而$y$没有的位的和,$odd=0,1$分别表示偶数,奇数。
那么对于每一位,有三种情况

  • 全为1(即xx=0,y=1,~y(在 &1 的情况下)= 0)
  • 有奇数个1(即xx=1,y=0,~y=1)
  • 有偶数个1(即xx=0,y=0,~y=1)

那么就有$3^{13}$个状态了,再乘上$odd$,也就是$2*3^{13}$个状态。

如何通过$xx$逆回$x$呢?
通过观察膜题解,可以发现

if(odd)x=xx|y;
else x=xx;

首先预处理出$3^{13}$的每一个状态,可以通过枚举~y的子集解决此问题。
状态转移方程显然,也就是state(xx,y)->state(x^a[i]&~(y&a[i]),y&a[i]))