题解：AT_agc057_c [AGC057C] Increment or Xor

· · 题解

题解

先考虑判无解，设 m=2^{n-1}，则一个排列能还原的一个必要条件是 p_i\equiv p_{i+m}\pmod{m}。证明考虑最终状态下一定是满足条件的，然后就是因为只有异或和 +1 操作，所以这个条件始终成立。

先考虑简单的情况，如果 \forall i\in[0,m),p_i 的最高位都是 0，那我们直接异或一个 p_0 就做完了。那如果不为零，我们就想去把它们全都变成零。从左到右考虑 [0,m) 的每个位置，考虑怎么操作才没有后效性？若当前考虑到了 i，前面 [0,i) 的最高位都变成了零，当前是 1，我们考虑用一些 +1 和异或把 1 变成 0 并且不影响其他位置的最高位。首先如果一直 +1 显然不行，所以我们最开始考虑异或。但是如果我们最高位异或上 1 那不就废了吗？这里我们可以先把 p_i 异或成 2^n-1，这样我们最高位异或上了一个零不会对其他地方有影响，然后我们全局 +1。这时候 p_i 会变成 0，考虑其他位置若是要最高位变成 1 那一定会产生进位。如果一个 p_j 要进位那么有 p_j=m-1，但是考虑我们的 p_i=2^n-1，那么就有 p_{i+m}=m-1，于是这样操作永远不会进位。并且这样操作次数不超过 2^n+1，非常优秀。

具体维护可以使用 01trie，时间复杂度 \mathcal O(n2^n)。