H. Hidden Track (Easy Version)
为啥这题要叫 Easy Version /yiw
题面非常唬人，其实考察的是翻译题面的能力。
首先大体读一遍，是要你求出隐藏的一个 \(0,1,...,n-1\) 的排列，并且保证 \(p_1。然后你的每次询问可以给出一个 \(m\) 和一个 \(v\)。什么作用先暂且不谈。反正给的 \(m\) 构造出了一个集合 \(S\)，然后把 \(S\) “异或”上 \(v\)。这里异或的意思是集合一个类似于异或的操作：一个集合异或这个数，就是看这个集合里有没有这个数，如果有就把他去掉，如果没有就把他加上。然后返回给你的值就是说，排列中两个相邻的元素有且仅有一个在 \(S\) 中的相邻的二元组数目，并且还要 \(\mod 3\)。那么我们逐层翻译：
第一个集合有什么特殊性？翻译第一个集合：只保留 \(m\) 的二进制位后有奇数个 \(1\) 的数。那代到 \(c(S)\) 中，就是说排列中的两个相邻元素中有且仅有一个只保留 \(m\) 的二进制位后有奇数个 \(1\)。那是不是就是只保留 \(m\) 的二进制位后二进制位下的 \(1\) 数目奇偶性不相等？我们再加入 \(v\)。首先如果 \(v\) 不等于任何 \(p_i\)，显然不会影响结果。但是如果 \(v=p_i\) 呢？因为 \(v=p_i\) 和 \(v=p_{i+1}\) 的效果是一样的，所以我们只需要考虑其中一个。那么就是在 \(S\) 异或 \(v\) 的情况下考虑。那么考虑一下影响的情况。就加入 \(v=p_i\)，那么 \(p_{i-1}\) 如果原本和他奇偶性不相等记作 \(p\)，\(p_{i+1}\) 原本和他奇偶性不相等记作 \(q\)。那么就是说。
- \(p\and q\) 这样弄贡献为 \(-2=1\pmod3\)
- \(p\or q\) 这样弄，贡献为 \(0\)
- \(\neg(p\and q)\) 这样弄贡献为 \(2\)
有这样的结论感觉非常好啊，因为刚好用到了题目里对 \(3\) 取模的性质。
我们自然而然的能想到，令 \(m\) 等于 \(2^i,i\in[0,k)\)。这里的 \(k\) 就是题目中的 \(k=\left\lceil\log_2n\right\rceil\)。那么我们不就弄清楚了每个数字左右两边的每一位有几个是 \(1\) 了吗。那么我们直接枚举开头的数，根据开头的数我们就能还原整个序列，最后验证一下答案合不合法就可以。