#P18959. [SEUSA2026] F. 密文计数(Ciphertext Count)

[SEUSA2026] F. 密文计数(Ciphertext Count)

密文计数(Ciphertext Count)

题目描述

给定一个仅含小写英文字母的字符串,作为一份报告。

一次单表替换是把 2626 个小写字母分别映射到 2626 个互不相同的小写字母,即字母表上的一个排列。允许一个字母映射到自身。加密字符串时,对每个字符使用同一个替换规则。

例如,某次替换把 p、a、e、r 分别替换为 t、i、l、e,便会把 paper 加密成 title。

每天可以从报告中选择一个非空连续子串,再任选一次单表替换,把它加密成一份密文。不同日期可以重复选择子串和替换,但不能发送重复的密文。

一共能产生多少种不同的密文?答案对 998244353998244353 取模。

输入格式

一行一个字符串,只包含小写英文字母,长度在 11 至 3×1053\times10^5 之间。

输出格式

输出一个整数,表示不同密文数量对 998244353998244353 取模的结果。

样例

aba
1326

子串 a、b 合起来能产生 2626 种单字母密文;ab、ba 合起来能产生 26×25=65026\times25=650 种两个不同字母组成的密文;aba 又能产生 650650 种首尾相同、中间不同的密文,总计 13261326。

decipher
834038017

来源

2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 F。

官方资料页 · 原题。中文根据用户提供的官方题面重新整理;全部测试数据来自赛事官方公开的数据包。