CF1117E Decypher the String题解

传送门

神奇的题。

这是一道交互题。
给定一个字符串 \(s\) , 我们拥有若干操作 , 但是你不知道 , 第 \(i\) 个操作形如 \(a_i,b_i\) 表示交换字符串 \(s\) 中的第 \(a_i\) 位和 \(a_j\) 位。
比如操作序列依次为 \((1,2),(2,3)\) ,给定字符串为 xyz 。
那么我们执行第一次操作后字符串变为 yxz ,而执行第\(3\)次操作后则变为 yzx 。
我们已经告知了你完成所有操作后的字符串序列,你需要还原其。
不过,你可以询问至多 \(3\) 次,每次询问你需要给出一个字符串,其长度与给定的字符串相等,然后我们会告诉你操作后的字符串序列。
数据范围:保证\(|s|\le 10^4\)。
输出答案需要加上 ! 。
查询操作则需要加上 ?。

首先我们直接忽略它的操作顺序。操作的结果可以看作给定一个数组 \(pos_i\)，操作后的串第 \(i\) 个字符实际上是原串的第 \(pos_i\) 个字符。

这个构造过于神奇了，所以直接写。

第一次：询问串 \(q_1=R(a\sim z)\)。假设返回的串为 \(r_1\)。把 \(a\sim z\) 看作 \(0\sim 25\)，若 \(r_1[i]=j\)，则必有 \(pos_i\equiv j\pmod {26}\)。因为所有 \(j\) 都在原串 \(\bmod 26=j\) 的位置上。

第二次：询问串 \(q_2=R(a\sim y)\)，得到 \(pos_i\equiv j'\pmod {25}\)。

第三次：询问串 \(q_3=R(a\sim w)\)，得到 \(pos_i\equiv j''\pmod {23}\)。

根据中国剩余定理，可以求出 \(pos_i\equiv {26\times 25\times 23}\)，因为 \(26\times 25\times 23>1000\)，所以可以唯一确定 \(pos_i\)，再倒回去还原即可。