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