← 返回题目列表

AtCoder · oupc2023_day1_e

E. 韩汉堡2

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

配点 : 100 点

問題文

N 字符或字符串 按此顺序连接的 X_1, X_2, \dots, X_N 字符串是 它被写为 X_1 + X_2 + \cdots + X_N 。
另外,字符串 X 的 i 从第一个字符开始 j 提取到字符的连续子字符串 X[i,j] 。
为字符串定义汉堡、整个汉堡和半个汉堡,如下所示。这个定义与问题D相同。

  • Burger 是一个完整汉堡的字符串,一个半汉堡的字符串。
  • 整个汉堡就是汉堡。 A 某些字符 可写为 c ,c + A + c 的字符串和空字符串
  • 半个汉堡是不是空的汉堡。 在可以写成 A、B ,A + B 的字符串中,不全是汉堡的字符串

例如,abba 呀 字符串是按顺序排列的字符串,例如 abbcca 都是汉堡,aabb 呀 字符串是按顺序排列的字符串,例如 abbacc 是半个汉堡,abbcbbc 呀 字符串是按顺序排列的字符串,例如 ababa 不是汉堡。

小写英文字母组成的字符串 S 和正整数 请回答以下有关 K 。k = 0, 1, 2, \dots, K 的问题。 一串小写字母,其中

  • S[i, j] + T 表示所有汉堡。 T 的最小可能长度是 k 变为 (i, j) (1 \leq i \leq j \leq |S|的数量) 除以 998244353 求余数。

制約

  • 1 \leq |S| \leq 200{,}000
  • 1 \leq K \leq 200{,}000
  • S 是一串小写字母
  • K 是一个整数

小課題

  1. ( 1 点) K \leq 300

  2. ( 99 点)无附加约束 请输出


入力

输入是按以下格式从标准输入给出的。 请输出超过

S
K

出力

K+1 行。 请在
i 输出 k = i-1 时输出答案。


入力例 1

abcc
3

出力例 1

1
5
3
1

S[i,j] + T 变成所有汉堡 T ,T 的最小长度是 k (0 \leq k \leq 3) 变为 每对 (i, j) 如下。 当

  • k = 0 时,(3, 4)
  • k = 1 时,(1, 1), (2, 2), (3, 3), (4, 4), (2, 4)
  • k = 2 时,(1, 2), (2, 3), (1, 4)
  • k = 3 时,(1, 3)

S[1, 4] = abcc 是T = ba 会给你所有的汉堡。T 的长度是 1 在以下情况下,它不会是一个完整的汉堡。

该测试用例满足子任务 1 的约束。


入力例 2

fortississimo
7

出力例 2

4
19
20
21
15
8
3
1

该测试用例满足子任务 1 的约束。