← 返回题目列表

Codeforces · 1184/A3

A3. 海蒂学习哈希(困难)

中文机器翻译题面 查看原题

现在海蒂已经准备好破解科瓦里安夫人的哈希函数了。

Kovarian 夫人对于姓名变更有一套非常严格的规则。仅当对两个名称使用以下哈希函数导致冲突时才可以互换。然而,散列函数是参数化的,因此人们总能找到一组导致此类冲突的参数。海蒂决定利用这一点为自己谋利。

给定两个字符串$$$w_1$$$、$$$w_2$$$,长度相等$$$n$$$,由小写英文字母和整数$$$m$$$组成。

考虑标准多项式哈希函数:

$$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)$$$

其中 $$$p$$$ 是某个素数,$$$r$$$ 是某个数字,例如 $$$2\leq r \leq p-2$$$。

目标是找到 $$$r$$$ 和素数 $$$p$$$ ($$$m \leq p \leq 10^9$$$) 使得 $$$H_p(w_1) = H_p(w_2)$$$。

字符串 $$$w_1$$$ 和 $$$w_2$$$ 是从长度为 $$$n$$$ 的小写英文字母的所有字符串中独立随机采样的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$10 \le n \le 10^5$$$, $$$2 \le m \le 10^5$$$)。

第二行和第三行分别包含单词 $$$w_1$$$、$$$w_2$$$,它们是从所有长度为 $$$n$$$ 的小写英文字母字符串中独立随机采样的。

输出

输出整数$$$p,r$$$。

$$$p$$$ 应该是 $$$[m, 10^9]$$$ 范围内的质数,$$$r$$$ 应该是满足 [2,p-2]$$$ 中 $$$r\ 的整数。

保证至少存在一个解决方案。如果存在多个解决方案,请打印其中任何一个。

示例

输入 #1

10 5
bgcbaaaaaa
cccaaaaaaa

输出 #1

5 2

输入 #2

10 100
melodypond
riversongg

输出 #2

118219 79724

注意

在第一个示例中,请注意,即使 $$$p=3$$$ 和 $$$r=2$$$ 也会导致哈希冲突,但这不是正确的解决方案,因为 $$$m$$$ 是 $$$5$$$,因此我们需要 $$$p\geq 5$$$。

在第二个示例中,我们注意到末尾有额外的“g”。我们只是没有意识到“River Song”和“Melody Pond”的长度不同......