思路

异或与普通加法的最低位奇偶性相同，而且异或值不会超过元素和。因此所有可能值都与 $n$ 同奇偶且不超过 $n$。

当 $m\ge3$ 时，对任意满足上述条件的 $x$，序列 $[x,(n-x)/2,(n-x)/2,0,\ldots,0]$ 都能得到异或值 $x$，所以这些必要条件也是充分条件。$m=1$ 时则只有值 $n$。

困难只在 $m=2$。

做法

设 $f(n)$ 为两个非负整数和为 $n$ 时所有可能异或值之和，$g(n)$ 为不同异或值的数量。

若 $n$ 为奇数，一数为奇、一数为偶。去掉最低位后得到和为 $(n-1)/2$ 的同类问题，因此

$$g(n)=g(\lfloor n/2\rfloor),\qquad f(n)=2f(\lfloor n/2\rfloor)+g(\lfloor n/2\rfloor).$$

若 $n$ 为正偶数，两数要么都为偶数，要么都为奇数。右移一位后，两类问题的和分别为 $n/2$ 与 $n/2-1$，并且得到的异或值最低位均为零，所以

$$g(n)=g(n/2)+g(n/2-1),$$ $$f(n)=2f(n/2)+2f(n/2-1).$$

初值为 $g(0)=1,f(0)=0$。记忆化计算只会访问每一二进制层常数个状态。

对于 $m\ge3$，若 $n=2k$，答案为 $k(k+1)$；若 $n=2k+1$，答案为 $(k+1)^2$。所有运算均对模数取模。

正确性证明

$m=1$ 的结论显然。$m\ge3$ 时，奇偶和上界给出所有可能异或值的必要范围，而三项构造对范围内每个值都给出合法序列，因此闭式求和完整且无重复。

$m=2$ 时，按两数最低位分类覆盖了全部可能且各类互不相交。右移后的和与异或值分别按递推式变化，数量和数值和的递推因此精确。以 $n=0$ 为初值递归即可得到全部可能值的数量与总和。

复杂度

每组数据的时间复杂度为 $O(\log n)$，记忆化状态的空间复杂度为 $O(\log n)$；$m\ne2$ 时为常数时间。