题解

思路

按二进制位考虑异或。某一位的异或为零，当且仅当这一位在偶数个 $A_i$ 中为一。如果当前位权为 $w$，选出 $2k$ 个数在这一位填一，会让总和增加 $2kw$，选择位置的方法数为 $\binom{N}{2k}$。

不同二进制位互不冲突：每个整数的各位可以独立决定。因此可以把每一位看成一个生成函数，再按总和做背包。

做法

令 $dp[s]$ 表示已经处理的二进制位使总和为 $s$ 的方案数，初始 $dp[0]=1$。依次枚举位权 $w=1,2,4,\ldots$，转移为

只保留总和不超过 $M$ 的状态。处理完所有不超过 $M$ 的位权后，$dp[M]$ 即为答案。

小规模子任务可以递归枚举所有和为 $M$ 的非负整数序列并检查异或。对于 $N=2$，异或为零要求两个数相等，所以 $M$ 为偶数时答案为 $1$，否则为 $0$。

正确性证明

对任意二进制位，转移只选择偶数个位置填一，所以构造出的序列在该位的异或为零；所有位都满足时整体异或为零。反过来，任意合法序列在每一位恰有偶数个一，且在该位选择这些位置的方式会被对应的组合数转移唯一计入。各位选择唯一确定每个 $A_i$，总和状态又恰好限制为 $M$，故 DP 与所有合法序列一一对应。

复杂度

时间复杂度为 $O(M^2\log M)$ 的直接上界，实际转移总量为各位可行偶数选择数之和；空间复杂度为 $O(M)$。