ARC066B Xor Sum

题意 ： 给出正整数 。

求出满足下列条件的数对 的数目 ：

• 存在 满足 。

答案对 取模。

，时限 。

---

由于异或是不进位的加法，故 。

所以所有合法数对必然有 ，只需进一步限制 即可。

记 为 时符合题意的 的个数。答案即为 。

考虑利用递推求解 。

边界 ： 。

• 若 是奇数，则 中必有且仅有一者为奇数。

  去掉 的最后一位，则相当于 。

  此时 。

• 若 是正偶数，则 或者全是偶数，或者全是奇数。

  去掉 的最后一位，则相当于 ：

  • （全偶） 。

  • （全奇） 。

  此时 。

已经可以 求解各个 。

记 ，目标是求出 。

考虑 的递推式 ：

• 为偶数

• 为奇数（且 ）

记忆化搜索即可，可以证明复杂度为 。