CF2210E Binary Strings are Simple?

本题为交互题。 你被给定了一个未知的二进制字符串 $s$，长度为 $n$。定义函数 $f(l, r)$ 为如下操作后数组 $a$ 中不同元素的个数： - 令 $S$ 为子串 $s_l s_{l+1} \ldots s_r$，子串长度为 $m$。 - 开始时数组 $a$ 为空。 - 对 $S$ 的每一次 $i$ 次左循环移位（$0 \leq i < m$），定义其逆序对数为 $x_{i}$。 - 对每个 $i$，将 $x_{i} \bmod m$ 添加到数组 $a$ 中，这里 $u \bmod v$ 表示 $u$ 除以 $v$ 的余数。 你可以通过发起询问来确定 $s$。每次询问，你可以选定两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），询问 $f(l, r)$ 的值。每次询问的代价为 $\dfrac{n}{r-l+1}$。注意代价不一定是整数。 你需要用不超过 $\mathbf{max(30,3\cdot n)}$ 的总询问代价确定隐藏的二进制字符串。你最多可以猜测 $2$ 次。 $^{\text{∗}}$ 二进制字符串只包含字符 $0$ 和 $1$。 $^{\text{†}}$ 设字符串 $s = s_{1}s_{2}\cdots s_{n}$。$s$ 的第 $k$ 次左循环移位定义为 $t_{k} = s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k}$。 $^{\text{‡}}$ 设字符串 $s = s_{1}s_{2}\cdots s_{n}$。$s$ 的逆序对数定义为满足 $1 \leq i < j \leq n$ 且 $s_{i} > s_{j}$ 的 $(i, j)$ 对数。

每组测例包含多组数据。第一行为测例数 $t$（$1 \leq t \leq 100$）。每组测例描述如下： 每组测例第一行是一个整数 $n$（$2 \leq n \leq 3000$），表示未知字符串 $s$ 的长度。 保证所有测例中 $n$ 的总和不超过 $3000$。 # 交互说明 若要发起查询，请输出如下格式的一行（不带引号）： - $\texttt{"? l r"}$（$1 \leq l \leq r \leq n$） 裁判将返回一个整数 $f(l,r)$。 当你猜测字符串 $s$（长度为 $n$）时，输出如下格式的一行（不带引号）： - $\texttt{"! s"}$ 若猜测正确，裁判将返回 $\texttt{1}$；否则返回 $\texttt{0}$。 猜测字符串不计算为查询。 如果你的猜测正确，则进行下一组数据，若已是最后一组，则程序结束。 交互器**非自适应**，即 $s$ 的答案在你询问前就已确定，并不会随你的提问发生变化。 每次输出查询或猜测语句后，**必须换行并刷新输出**。否则你将因“程序空闲超限”被判为无效。 如任何交互步骤读取到 $-1$ 而不是有效数据，你应立即退出程序。这表示你的查询无效或其他错误。若未立即退出，可能因对已关闭的流继续操作导致任意结果。 $^{\text{∗}}$ 刷新输出方式如下： - C++：`fflush(stdout)` 或 `cout.flush()` - Python：`sys.stdout.flush()` - 其它语言请查阅文档。

（与输入格式一致，根据交互要求发起询问或给出答案，每次操作后请输出换行并刷新输出。）

在例交互中，输入和输出间有空行以对齐交互器响应。实际交互输入输出中，这些空行不会出现。 第一组数据中，隐藏字符串为 $s=00000$。由于全为 0 不会产生逆序对，任意子串的 $a$ 始终为 $[0]$，因此所有 $f(l, r)$ 的返回值均为 $1$。 此例中共发起了 $3$ 次查询： - 首次查询 $f(1,5)$，返回 $1$，查询代价 $= \dfrac{5}{5-1+1}=1$。 - 第二次查询 $f(2,5)$，返回 $1$，查询代价 $= \dfrac{5}{5-2+1}=\dfrac{5}{4}$。 - 第三次查询 $f(3,5)$，返回 $1$，查询代价 $= \dfrac{5}{5-3+1}=\dfrac{5}{3}$。 总询问代价 $= 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12}$，小于 $\max(30, 3 \cdot n) = 30$。 之后我们猜测 $s=00000$，交互器返回 $1$，表示猜测正确，进行下一组数据。 第二组数据，隐藏串为 $s=001$。 我们询问 $f(1,3)$，返回 $3$。查询代价 $= \dfrac{3}{3-1+1}=1$。 总查询代价为 $1$，小于 $\max(30, 3 \cdot n)=30$。 然后我们猜测 $100$，交互器返回 $0$，表示猜测错误。 再猜测 $001$，交互器返回 $1$，表示猜测正确，进入下一组数据。 第三组数据，隐藏串为 $s=10101010$。 由 ChatGPT 5 翻译