都说状压DP是显然的

我们把每个数变成一个 0~2^19-1 的状态。

定义：

dp[x]

表示当前处理的数中，选一些数，使它们异或结果为 x 的方案数。

初始：

dp[0]=1;

表示一个数都不选，异或和为 0。

处理一个新的状态 s 时：

• 不选它：异或还是 x
• 选它：异或变成 x^s

所以：

ndp[x]+=dp[x];
ndp[x^s]+=dp[x];

最后 dp[0] 就是异或为 0 的方案数，再减去空集。