AtCoder 补题记录
天坑。
AGC 057
C - Increment or Xor
从低到高位建 01 Trie，第 \(i\) 个叶子存着值为 \(i\) 的位置。
考虑两种操作：
- 操作 A：交换某些深度所有节点的左右儿子（即异或某个数）
- 操作 B：交换两个同父亲的叶子，同时不改变其他叶子的左右儿子关系（把这个叶子异或上某个数后挪到 \(2^n-1\) 去，然后 \(+1\) 来交换左右叶子）
操作 A 不会应用在最后一层（可以被 \(+2^{n-1}\) 替代），同时根据 \(i\) 所在位置与 \(i+2^{n-1}\) 所在位置的关系，可以确定每组左右叶子是否交换，即 B 操作已经固定了。
模拟完 B 操作后，最后再用 \(1\) 次 A 操作即可。