← 返回题目列表

Codeforces · 1994/H

H. 堡垒之夜

中文机器翻译题面 查看原题

这是一个交互问题!

Timofey 正在编写一项名为“Capture the Flag”(简称 CTF)的竞赛。他还剩下一项任务,涉及入侵安全系统。整个系统基于多项式哈希$$$^{\text{*}}$$$。

Timofey 可以向系统输入一个由小写拉丁字母组成的字符串,系统将返回其多项式哈希。为了破解系统,Timofey 需要找到系统使用的多项式哈希参数($$$p$$$ 和 $$$m$$$)。

Timofey 的时间不多了,所以他只能进行 $$$3$$$ 查询。帮助他解决任务。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$ 的查询?,否则您将得到错误答案的结论。

输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到超出空闲限制的判决。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

示例

输入 #1

1

32

28

输出 #1

? aa

? yb

! 31 59

注意

第一个查询的答案是 $$$(ord(a) \cdot 31^0 + ord(a) \cdot 31^1) \mod 59 = (1 + 1 \cdot 31) \mod 59 = 32$$$。

第二个查询的答案是 $$$(ord(y) \cdot 31^0 + ord(b) \cdot 31^1) \mod 59 = (25 + 2 \cdot 31) \mod 59 = 28$$$。