题目描述
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跨年赛