#P6042. 字符串

    ID: 6434 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100省选/NOI-欧拉路径带权二分图匹配交换论证对称性分析后缀数组Kasai 算法Hierholzer 算法高精度加法高精度减法

字符串

题目背景

小 W 喜欢字符串。

题目描述

小 W 有一个只包含大写字母的字符串 SS。

如果字符串 TT 只包含大写字母和数字 0 到 9,长度为 KK,并且将其中每个数字 ii 替换成第 i+1i+1 个大写字母后,得到的字符串是 SS 的子串,就称 TT 是好的。例如,数字 0 替换为 A,数字 9 替换为 J。

求一个最短的字符串 AA,使所有好的字符串都是 AA 的子串。

输入格式

一行,依次给出 SS、KK 和 type\mathrm{type}。

输出格式

  • 若 type=1\mathrm{type}=1,输出一个整数,表示 AA 的最小长度对 109+710^9+7 取模后的结果。
  • 若 type=2\mathrm{type}=2,输出任意一个满足条件的最短字符串 AA。AA 只能包含大写字母和数字。

样例

OOOP 2 2
OOP
AB 1 1
4

样例 2 中,A、B、0、1 都是好的字符串,因此长度至少为 44。AB01 是一个达到该长度的答案。

数据范围

∣S∣≤5000|S|\le5000,1≤K≤5001\le K\le500,K≤∣S∣/2K\le |S|/2,type∈{1,2}\mathrm{type}\in\{1,2\}。

若 type=2\mathrm{type}=2,SS 中不出现前 1010 个大写字母。

子任务 ∣S∣\lvert S\rvert 上限 type\mathrm{type} 特殊性质 分值
1 10 1 SS 仅包含 O 和 P 10
2 100 2 无 30
3 5000
4 1

原 PDF 题面