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 翻译