#PQJ932x4057. QOJ 932_4057

    ID: 3070 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2022字符串前缀和

QOJ 932_4057

小 D 四岁半的时候学会了后缀自动机。

你有一个字符串 𝑆 ,长度为 𝑛 。初始时, 𝑇 0

𝑆 。每次你可以删除 𝑇 𝑖 的开头或结尾的字符得到新的字符串 𝑇 𝑖 + 1 ,经过 𝑛 − 1 次操作之后,我们会得到只有一个字符的串 𝑇 𝑛 − 1 ,根据每次删除的选择,一共有 2 𝑛 − 1 中可能的操作序列。注意,虽然可能会有一次操作,删除开头或结尾的字符得到相同的串,但是我们仍然把它当成两种不一样的操作序列。

对于一个串 𝑇 ,我们记 𝑜 𝑐 𝑐 ( 𝑇 ) 表示 𝑇 在 𝑆 中作为子串的出现次数,比如 𝑜 𝑐 𝑐 ( aaa , aaabaaa )

3 。

对于一个操作序列,记它的贡献是 ∏ 𝑖

1 𝑛 − 1 𝑜 𝑐 𝑐 ( 𝑇 𝑖 ) ,求所有操作序列的贡献和,由于答案很大,输出对 998 244 353 取模的结果。

输入格式

一共一行,包含一个字符串 𝑆 ,保证 𝑆 只包含小写字符。

输出格式

一行一个整数,表示答案。

样例数据 样例 1 输入 zzz 样例 1 输出 24 样例 2 输入 abbab 样例 2 输出 53 样例 3

见下发文件。

子任务

一共 20 个测试点。

对于测试点 1 ∼ 5 ,满足 | 𝑆 | ≤ 5 000 。

对于测试点 6 ∼ 8 ,满足 𝑆 的每个字符从 a 和 b 中等概率独立随机生成。

对于测试点 9 ∼ 14 ,满足 | 𝑆 | ≤ 6 × 10 4 。

对于所有数据, 1 ≤ | 𝑆 | ≤ 10 5 。