edu157D

• 原题链接：Problem - D - Codeforces

• 题意

  • 求解XOR 给数组 a ，要求找到数组b满足
    • b[i] 异或 b[i + 1] == a[i]
    • b为由0到sizeof(a)的集合构成
      • 即每个数有且只有一个

• 思路

  • 发现
    • $b_1⨁b_2=a_1$
    • $b_1⨁b_3=a_1⨁a_2$
    • $b_1⨁b_4=a_1⨁a_2⨁a_3$
    • …
  • 于是有
    • 求得b1就可以求得b数组
    • 前缀和求a数组运算

  • 求b1

    • 求b1要看到异或的性质
    • 假设b1在某一位置上是0，那么b1 异或上其他数的得到结果
      • 结果上的该位的是1是0取决于异或上的数是1还是0
      • 如果是一堆数与b1运算，那么结果的该位上1的总数与参与运算的数中1的总数相同
      • 即 只要查得 b2 - bn 中，某一位上1的总数 是否与结果（前缀和）中1的总数相同 就可以得到b1在该位上是0还是1

• 实现

  • edu157D.cpp