1553 : 字符串的哈希碰撞

时间限制:1 Sec 内存限制:256 MiB 提交:56 正确:17

提交 状态 论坛

题目描述

Hash Function介绍(摘自OI wiki):

我们定义一个把字符串映射到整数的函数$f$,这个$f$称为是 Hash 函数。

我们希望这个函数$f$可以方便地帮我们判断两个字符串是否相等。

具体来说,哈希函数最重要的性质可以概括为下面两条:

1.在 Hash 函数值不一样的时候,两个字符串一定不一样;

2.在 Hash 函数值一样的时候,两个字符串不一定一样(但有大概率一样,且我们当然希望它们总是一样的)。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

通常我们采用的是多项式 Hash 的方法,对于一个长度为$n$的字符串$s$来说,我们可以这样定义多项式 Hash 函数:$f(s)=\sum_{i=1}^{n}{s[i]\times base^{n-i}}(mod  M)$。例如,对于字符串"xyz",其哈希函数值为 $(xb^2+yb+z) % M$。


在本题中,我们选定$base=2023,M=998244353$,现在给定$k$个非空字符串(仅包含小写英文字母),请你判断使用2023字符串哈希函数时,这些字符串的哈希值是否会发生哈希碰撞?


注:C/C++中字符编码为ASCII,请将字符的值看作对应ASCII码的值。

输入描述

第一行一个整数$k(1\le k\le 10^5)$,表示给定非空字符串的个数。

接下来$k$行,每行一个字符串。

保证$k$个字符串的长度不超过$10^6$。

输出描述

如果没有发生哈希碰撞,输出"2023:Will be a nice year!",否则输出"2023:Just give it a try!"。

样例输入

3
happy
new
year

样例输出

2023:Will be a nice year!

来源

2023跨年赛