#P18950. [Mladen Manev 2021 B4] hashing / 恢复哈希参数
[Mladen Manev 2021 B4] hashing / 恢复哈希参数
恢复哈希参数
这是交互题。一个隐藏哈希函数的参数为整数 ,满足 、。对于小写英文字母串 ,定义
$$F(S)=\left(\sum_{i=0}^{|S|-1}v(S_i)B^i\right)\bmod M,$$其中 ,字符串下标从零开始。注意左端字符对应 。
每局最多询问 10 次,每次给出一个长度为 至 的小写字母串,交互器返回其哈希值。你需要恢复确切的 。一个测试包含 局,,每局参数独立固定。
交互协议
首先读入 。当前局询问时输出 ? S,刷新输出,读入 。
确定参数后输出 ! B M 并刷新输出。如果还有下一局,立即开始下一局的询问,不会再次读入局数。全部 局结束后退出。最终回答不计入询问次数。
交互示意
若当前参数为 ,询问 ? aa 会得到 8。只有得到足够信息后才能输出 ! 7 1234567890。
题包说明
原题为 play(t)、calculate_hash、submit_hash 函数交互,本题包采用等价的标准流协议。隐藏输入为 及 对参数,由交互器独占读取。原比赛按正确完成的局数给部分分;本题包将全部测试捆绑成一个 100 分子任务,必须全部答对才得到满分。
来源与数据说明
2021 年 Dr. Mladen Manev,B4,原题名 hashing。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。