AT_oupc2023_day1_e.Han Burger 2

将 $N$ 个字符或字符串 $X_1, X_2, \dots, X_N$ 按照顺序连接得到的字符串记作 $X_1 + X_2 + \cdots + X_N$。
此外，字符串 $X$ 的第 $i$ 个字符到第 $j$ 个字符组成的连续子串记作 $X[i, j]$。
对于字符串，定义“バーガー(Burger)”、“全バーガー(Full Burger)”和“半バーガー(Half Burger)”如下。该定义与 D 问一样。

• “バーガー(Burger)” 指的是“全バーガー(Full Burger)”和“半バーガー(Half Burger)”的字符串。
• “全バーガー(Full Burger)” 指存在某个“バーガー(Burger)” $A$ 和某个字符 $c$，使得字符串可表示为 $c+A+c$，或是空字符串。
• “半バーガー(Half Burger)” 指的是可以表示为非空“バーガー(Burger)” $A$ 和 $B$ 拼接而成 $A+B$ 的字符串，且不是“全バーガー(Full Burger)”的字符串。

例如，abba 和 abbcca 是“全バーガー(Full Burger)”，aabb 和 abbacc 是“半バーガー(Half Burger)”，而 abbcbbc 和 ababa 不属于“バーガー(Burger)”。

给定一个由小写英文字母组成的字符串 $S$ 和正整数 $K$，请对于 $k = 0, 1, 2, \dots, K$，回答下述问题：

• 求 $S[i, j] + T$ 变成“全バーガー(Full Burger)”所需补充的 $T$（为任意小写英文字母字符串）最短长度为 $k$ 的 $(i, j)$（$1 \leq i \leq j \leq |S|$）的组数，并对 $998244353$ 取模。

输入以如下格式从标准输入读入：

$S$ $K$

请输出 $K+1$ 行。
第 $i$ 行输出 $k = i-1$ 时的答案。

小题目

1. ($1$ 分) $K \leq 300$
2. ($99$ 分) 没有其他限制

样例解释 1

对于 $S[i, j] + T$ 变为“全バーガー(Full Burger)”的 $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$ 可变为“全バーガー(Full Burger)”。$T$ 长度不超过 $1$ 时无法成为“全バーガー(Full Burger)”。

该样例满足小题目 1 的限制。

样例解释 2

该样例满足小题目 1 的限制。

数据范围

• $1 \leq |S| \leq 200{,}000$
• $1 \leq K \leq 200{,}000$
• $S$ 由小写英文字母组成
• $K$ 为整数

由 ChatGPT 5 翻译