{"problem":{"name":"[SDOI/SXOI2022] 子串统计","description":{"content":"小 D 四岁半的时候学会了后缀自动机。 你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8351"},"statements":[{"statement_type":"Markdown","content":"小 D 四岁半的时候学会了后缀自动机。\n\n你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相同的串，但是我们仍然把它当成两种不一样的操作序列。\n\n对于一个串 $T$，我们记 $\\operatorname{\\textit{occ}}(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数，比如 $\\operatorname{\\textit{occ}}(\\texttt{aaa},\\texttt{aaaabaaa})=3$。\n\n对于一个操作序列，记它贡献是\n\n$$\\prod_{i = 1}^{n - 1} \\operatorname{\\textit{occ}}(T_i)$$\n\n求出所有操作序列的贡献和，由于答案很大，请输出答案对 $998244353$ 取模的结果。\n\n## Input\n\n只有一行一个字符串 $S$，保证只包含小写字符。\n\n## Output\n\n输出一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n### 数据规模与约定\n\n本题共 $20$ 个测试点。\n\n- 对于测试点 $1\\sim 5$，满足 $|S| \\le 5000$。\n- 对于测试点 $6\\sim 8$，满足 $S$ 的每个字符均从 $\\texttt a$ 和 $\\texttt b$ 中等概率独立随机生成。\n- 对于测试点 $9\\sim 14$，满足 $|S| \\le 6 \\times 10^4$。\n\n对于所有数据，$1 \\le |S| \\le 10^5$。$S$ 中只有小写英文字母。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8351","tags":["各省省选","2022","山东","O2优化","山西"],"sample_group":[["zzz\n","24\n"],["abbab\n","53\n"],["见附加样例文件中的 ex_substring3.in","见附加样例文件中的 ex_substring3.out"]],"created_at":"2026-03-03 11:09:25"}}