4956.#6233. Hash killer V

时间限制:1s 内存限制:256MB

你的 $NOIp(plus)$ 模拟赛中有这么一道题:

快速判断两个串是否相同。串中全是小写字母。

大头看到了,这 $tm$ 不是哈希傻逼题吗?
于是大头交了一发 $Hash$ 上来。
程序如下:

   S->read(); T->read(); fl->0; 
   If (s.length()!=t.length()) fl->1; 
   Bas->26 mo[1..N]->//一大堆的正整数(输入数据会告诉你的)。 
   For i->1 to s.length() 
     For j->1 to N 
      hsh[1][j]->(hsh1[1][j]*bas+S[i]-'a')%mo[j] 
      hsh[2][j]->(hsh2[2][j]*bas+T[i]-'a')%mo[j] 
   For i->1 to N 
     If hsh[1][i]!=hsh[2][i] fl->1; 
   If fl write(NO); 
   Else write(YES);

大头坚信自己程序能 $AC$ (除非他肤色过深那就嘿嘿嘿)。
但是你还是决定面向程序一发 。
你打算重构你的 $20$ 组数据,使得标准答案全是 $NO$ ,但是大头的输出全是 $YES$ ,给大头一个惊喜。

输入格式(从终端/标准输入读取)

第一行一个数 $N$ 。
接下来一行 $N$个数,第 $i$ 个数表示 $mo_i$ 。

输出格式(输出至终端/标准输出)

两行,一行一个字符串,字典序越小越好。

输入样例

复制
2
2 3
 \n
 · \n

输出样例

复制
a
g
 \n
 \n

说明

这里有个绝妙的解释,可是空间太小写不下。

数据范围与提示

对于 $100%$ 的数据,$1≤n≤1000,1≤mo_i ≤5×10^{17} 。

当然,为了提高难度,你的答案必须保证最优。

即保证第一个字符串在长度尽可能小的情况下字典序尽量小。

在第一个字符串相同的情况下保证第二个字符串在长度尽量小的情况下字典序尽量小。

否则你的答案可能会被判为 $0$ 分。

来源: LOJ

提交题解

Please login first.

© 2025 FAQs