#P3099. Hash Killer III

    ID: 2219 传统题 1000ms 128MiB 尝试: 933 已通过: 1 难度: 7 上传者: 标签>难度分类提高字符串字符串哈希模拟与实现技巧进位制转换枚举与搜索暴力枚举构造与建模分块构造CF2300

Hash Killer III

P3099 Hash Killer III

题目背景

VFleaKing 想统计一个字符串中不同的定长连续子串的数量。他使用了双模数多项式哈希,并通过排序去重哈希值来计算答案。

你需要构造一组数据,使这一做法得到错误的答案。

题目描述

给定一个长度为 nn 的小写字母字符串 ss 和整数 ll,正确答案是 ss 中互不相同的、长度恰好为 ll 的连续子串的数量。

两个子串不同,当且仅当它们存在某个对应位置上的字符不同。

VFleaKing 对每个长度为 ll 的子串计算两个多项式哈希值,将有序数对 (h1,h2)(h_1,h_2) 作为子串的标识,再对所有有序数对排序、去重,以去重后的数量作为答案。

对于一个字符串 t=t0t1⋯tl−1t=t_0t_1\cdots t_{l-1},单模数哈希定义为

$$H_{B,P}(t)=\left(\sum_{i=0}^{l-1}x_i B^{l-1-i}\right)\bmod P.$$

其中字母 a 到 z 分别对应整数 00 到 2525,xix_i 是 tit_i 对应的整数,BB 是哈希基数,PP 是模数。连续子串的哈希值可以通过滚动哈希计算。

本题的 Special Judge 会检查下列全部组合:

  • 基数 B∈{31,62,51,73,101,125}B\in\{31,62,51,73,101,125\},共有 66 种;
  • 模数从 {1000000007,1000000009,2147483647}\{1000000007,1000000009,2147483647\} 中选取两个不同的模数,共 (32)=3\binom{3}{2}=3 种;
  • 共需检查 6×3=186\times3=18 种双哈希配置。

你输出的同一组数据,必须使上述 18 种配置的哈希去重结果均严格小于真实的不同子串数量,才算正确。

输出任意一组满足要求的数据即可。

输入格式

无输入。

输出格式

你的程序向标准输出写两行。

第一行输出两个整数 n,ln,l,用空格分隔。

第二行输出一个长度恰好为 nn、仅包含小写英文字母 a 到 z 的字符串 ss。

满足

1≤l≤n≤105.1\le l\le n\le 10^5.

样例

原题给出下列输出格式示意。这两行会被判为错误。

8 4
buaabuaa

提示

本题提交源程序。评测系统运行你的程序,并使用 Special Judge 判定其输出。

可以从多项式哈希的碰撞条件入手:当两个不同字符串对应的多项式数值之差能够被某个模数整除时,它们在该模数下的哈希值相同。