#P18950. [Mladen Manev 2021 B4] hashing / 恢复哈希参数

[Mladen Manev 2021 B4] hashing / 恢复哈希参数

恢复哈希参数

这是交互题。一个隐藏哈希函数的参数为整数 B,MB,M,满足 2≤B≤1002\le B\le100、109≤M≤2⋅10910^9\le M\le2\cdot10^9。对于小写英文字母串 SS,定义

$$F(S)=\left(\sum_{i=0}^{|S|-1}v(S_i)B^i\right)\bmod M,$$

其中 v(a)=1,…,v(z)=26v(\texttt{a})=1,\ldots,v(\texttt{z})=26,字符串下标从零开始。注意左端字符对应 B0B^0。

每局最多询问 10 次,每次给出一个长度为 11 至 100100 的小写字母串,交互器返回其哈希值。你需要恢复确切的 B,MB,M。一个测试包含 TT 局,1≤T≤201\le T\le20,每局参数独立固定。

交互协议

首先读入 TT。当前局询问时输出 ? S,刷新输出,读入 F(S)F(S)。

确定参数后输出 ! B M 并刷新输出。如果还有下一局,立即开始下一局的询问,不会再次读入局数。全部 TT 局结束后退出。最终回答不计入询问次数。

交互示意

若当前参数为 B=7,M=1234567890B=7,M=1234567890,询问 ? aa 会得到 8。只有得到足够信息后才能输出 ! 7 1234567890。

题包说明

原题为 play(t)、calculate_hash、submit_hash 函数交互,本题包采用等价的标准流协议。隐藏输入为 TT 及 TT 对参数,由交互器独占读取。原比赛按正确完成的局数给部分分;本题包将全部测试捆绑成一个 100 分子任务,必须全部答对才得到满分。

来源与数据说明

2021 年 Dr. Mladen Manev,B4,原题名 hashing。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。