A6597. 「SDOI / SXOI2022」子串统计
编程题
NOI/NOI+/CTSC
知识点
题目描述
小 D 四岁半的时候学会了后缀自动机。
你有一个字符串 $S$，长度为 $n$。初始时，$T_0 = S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i+1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n-1}$，根据每次删除的选择，一共有 $2^{n-1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相同的串，但是我们仍然把它当成两种不一样的操作序列。
对于一个串 $T$，我们记 $\operatorname{occ}(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数，比如 $\operatorname{occ}(\mathtt{aaa,aaaabaaa})=3$。
对于一个操作序列，记它贡献是
$$ \prod_{i=1}^{n-1} \operatorname{occ}\left(T_{i}\right) $$
求出所有操作序列的贡献和，由于答案很大，请输出答案对 $998244353$ 取模的结果。
你有一个字符串 $S$，长度为 $n$。初始时，$T_0 = S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i+1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n-1}$，根据每次删除的选择，一共有 $2^{n-1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相同的串，但是我们仍然把它当成两种不一样的操作序列。
对于一个串 $T$，我们记 $\operatorname{occ}(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数，比如 $\operatorname{occ}(\mathtt{aaa,aaaabaaa})=3$。
对于一个操作序列，记它贡献是
$$ \prod_{i=1}^{n-1} \operatorname{occ}\left(T_{i}\right) $$
求出所有操作序列的贡献和，由于答案很大，请输出答案对 $998244353$ 取模的结果。
输入格式
只有一行一个字符串 $S$，保证只包含小写字符。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
zzz
输出 #1
24
输入 #2
abbab
输出 #2
53
说明/提示
本题共 $20$ 个测试点。
- 对于测试点 $1 \sim 5$，满足 $|S| \leq 5000$。
- 对于测试点 $6 \sim 8$，满足 $S$ 的每个字符均从 $\mathtt{a}$ 和 $\mathtt{b}$ 中等概率独立随机生成。
- 对于测试点 $9 \sim 14$，满足 $|S| \leq 6 \times 10^{4}$。
对于所有数据，$1 \leq|S| \leq 10^{5}$。$S$ 中只有小写英文字母。
- 对于测试点 $1 \sim 5$，满足 $|S| \leq 5000$。
- 对于测试点 $6 \sim 8$，满足 $S$ 的每个字符均从 $\mathtt{a}$ 和 $\mathtt{b}$ 中等概率独立随机生成。
- 对于测试点 $9 \sim 14$，满足 $|S| \leq 6 \times 10^{4}$。
对于所有数据，$1 \leq|S| \leq 10^{5}$。$S$ 中只有小写英文字母。