先考虑判无解，设 $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)$。