#P3099. Hash Killer III
Hash Killer III
P3099 Hash Killer III
题目背景
VFleaKing 想统计一个字符串中不同的定长连续子串的数量。他使用了双模数多项式哈希,并通过排序去重哈希值来计算答案。
你需要构造一组数据,使这一做法得到错误的答案。
题目描述
给定一个长度为 的小写字母字符串 和整数 ,正确答案是 中互不相同的、长度恰好为 的连续子串的数量。
两个子串不同,当且仅当它们存在某个对应位置上的字符不同。
VFleaKing 对每个长度为 的子串计算两个多项式哈希值,将有序数对 作为子串的标识,再对所有有序数对排序、去重,以去重后的数量作为答案。
对于一个字符串 ,单模数哈希定义为
$$H_{B,P}(t)=\left(\sum_{i=0}^{l-1}x_i B^{l-1-i}\right)\bmod P.$$其中字母 a 到 z 分别对应整数 到 , 是 对应的整数, 是哈希基数, 是模数。连续子串的哈希值可以通过滚动哈希计算。
本题的 Special Judge 会检查下列全部组合:
- 基数 ,共有 种;
- 模数从 中选取两个不同的模数,共 种;
- 共需检查 种双哈希配置。
你输出的同一组数据,必须使上述 18 种配置的哈希去重结果均严格小于真实的不同子串数量,才算正确。
输出任意一组满足要求的数据即可。
输入格式
无输入。
输出格式
你的程序向标准输出写两行。
第一行输出两个整数 ,用空格分隔。
第二行输出一个长度恰好为 、仅包含小写英文字母 a 到 z 的字符串 。
满足
样例
原题给出下列输出格式示意。这两行会被判为错误。
8 4
buaabuaa
提示
本题提交源程序。评测系统运行你的程序,并使用 Special Judge 判定其输出。
可以从多项式哈希的碰撞条件入手:当两个不同字符串对应的多项式数值之差能够被某个模数整除时,它们在该模数下的哈希值相同。