CF1748F Circular Xor Reversal
yzxoi
2022-11-14 (Updated: 2022-11-14)
给定整数 n。初始，有一个编号从 0 开始的长度为 n 的环形序列 a，满足 a_i=2^i 对任意整数 i(0leq i<n)a 翻转，即使序列 a 满足 a_i=2^{n-i-1} 对任意整数 i(0leq i<n)2.5times10^5 次：
- 选定整数 i，将 a_i 的值改为 a_itext{ xor }a_{(i 1)bmod n}。其中 text{xor} 表示按位异或运算。
可以证明在题目限制下，本题一定有解。你需要找出任意一组满足要求的解。
nleq 400。
Tutorial
容易想到交换两个数：xoplus =y,yoplus =x,xoplus =y。
考虑 a_i leftarrow a_ioplus a_j。
将 irightarrow j 的路径抠出来，设为 irightarrow s_1rightarrow s_2rightarrow cdots rightarrow s_k rightarrow j。
容易找到一种简单的构造方式：
- s_k rightarrow i。
- s_1 rightarrow s_k
- s_{k-1}rightarrow i
- s_{1}rightarrow s_{k-1}
注意到这样的操作次数可能有冗余。
容易发现最后对于每一对交换只要求相对顺序即可。
可以分别抠出来，注意到最后一步可以与下一对的第一步抵消。
180961843
