#PQJ932x4057. QOJ 932_4057
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 。