CF1994H Fortnite

这是一个交互题！ Timofey 正在编写一场名为 Capture the Flag（简称 CTF）的比赛。他还剩下最后一道题，这道题涉及到破解一个安全系统。整个系统基于多项式哈希 $^{\text{∗}}$。 Timofey 可以向系统输入一个由小写拉丁字母组成的字符串，系统会返回它的多项式哈希值。为了破解系统，Timofey 需要找出系统使用的多项式哈希参数（$p$ 和 $m$）。 Timofey 时间不多了，所以他最多只能进行 $3$ 次查询。请你帮助他完成这道题。 $^{\text{∗}}$ 一个长度为 $n$ 的小写拉丁字母字符串 $s$ 的多项式哈希值，基于 $p$ 并对 $m$ 取模，定义为 $(\mathrm{ord}(s_1) \cdot p^0 + \mathrm{ord}(s_2) \cdot p^1 + \mathrm{ord}(s_3) \cdot p^2 + \ldots + \mathrm{ord}(s_n) \cdot p^{n-1}) \bmod m$。其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符，$\mathrm{ord}(\mathrm{chr})$ 表示字符 $\mathrm{chr}$ 在英文字母表中的序号，$x \bmod m$ 表示 $x$ 除以 $m$ 的余数。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^3$）——表示测试用例的数量。 保证系统使用的 $p$ 和 $m$ 满足条件：$26 < p \leq 50$ 且 $p + 1 < m \leq 2 \cdot 10^9$。

每次向系统查询时，输出 ? $s$，其中 $s$ 是你想要查询哈希值的字符串，长度不超过 $50$ 个字符。系统会返回字符串 $s$ 的多项式哈希值。 输出答案时，输出 ! $p$ $m$，其中 $p$ 是哈希的底数，$m$ 是模数。之后立即进入下一个测试用例。 你最多只能进行 $3$ 次查询 ?，否则会得到 Wrong Answer 判定。 每次输出查询后，别忘了输出换行并刷新输出缓冲区。否则会收到 Idleness limit exceeded 判定。刷新缓冲区的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。

第一次查询的答案为 $(\mathrm{ord}(a) \cdot 31^0 + \mathrm{ord}(a) \cdot 31^1) \bmod 59 = (1 + 1 \cdot 31) \bmod 59 = 32$。 第二次查询的答案为 $(\mathrm{ord}(y) \cdot 31^0 + \mathrm{ord}(b) \cdot 31^1) \bmod 59 = (25 + 2 \cdot 31) \bmod 59 = 28$。 由 ChatGPT 4.1 翻译