CF1815D XOR Counting 题解

第一眼感觉非常神秘！直接考虑找性质！ 考虑如何拼凑出异或和 $x$，直接令 $a_1=x$，则我们要把 $n-x$ 分配到剩下的 $m-1$ 个数中，让它们异或和为 $0$，如果 $n-x$ 是奇数，显然无解，否则可以构造 $2$ 个 $\frac{n-x}{2}$，剩下的 $a$ 直接取 $0$。 发现这个方法的前提是 $m\ge3$，答案为小于等于 $n$ 的数中所有与 $n$ 模 $2$ 同余的数之和，可以 $O(1)$ 计算。 然后发现当 $m=1$ 时显然答案为 $n$。 所以只需考虑 $m=2$ 时的情况。 考虑 dp，令 $f_{i,j},g_{i,j}$ 分别表示在前 $i$ 个二进制位中满足向 $i+1$ 位进位为 $j$ 的答案和方案数。记按照 $n$ 在二进制下第 $i$ 位的数值为 $o_i$，则可以根据 $o_i$ 分讨转移。具体地，若 $o_{i+1}=j$，此时在 $i+1$ 位可以都放 $1$ 或都放 $0$，进位分别为 $1,0$，有转移 $g_{i+1,1}\gets g_{i+1,1}+g_{i,j},g_{i,0}\gets g_{i+1,0}+g_{i,j}$，$f$ 的转移同理，另一种情况类似，不再赘述。需要注意的是，当 $o_{i+1}\neq j$ 时，放 $1$ 会使 $f$ 增加 $2^{i+1}g_{i,j}$ 的贡献。最终答案即为 $f_{60,0}$（$2^{60}>10^{18}$）。 复杂度 $O(T\log n)$。 [Code](https://codeforces.com/contest/1815/submission/230180415)