CF1748F Circular Xor Reversal
CF1748F Circular Xor Reversal
yzxoi
2022-11-14 (Updated: 2022-11-14)
给定整数 n。初始，有一个编号从 0 开始的长度为 n 的环形序列 a，满足 a_i=2^i 对任意整数 i(0\leq i<n)a 翻转，即使序列 a 满足 a_i=2^{n-i-1} 对任意整数 i(0\leq i<n)2.5\times10^5 次：
- 选定整数 i，将 a_i 的值改为 a_i\text{ xor }a_{(i+1)\bmod n}。其中 \text{xor} 表示按位异或运算。
可以证明在题目限制下，本题一定有解。你需要找出任意一组满足要求的解。
n\leq 400。
Tutorial
容易想到交换两个数：x\oplus =y,y\oplus =x,x\oplus =y。
考虑 a_i \leftarrow a_i\oplus a_j。
将 i\rightarrow j 的路径抠出来，设为 i\rightarrow s_1\rightarrow s_2\rightarrow \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}
注意到这样的操作次数可能有冗余。
容易发现最后对于每一对交换只要求相对顺序即可。
可以分别抠出来，注意到最后一步可以与下一对的第一步抵消。
本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-14
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录