#P18835. [Croatian CPC2019] Jaki Jovsi
[Croatian CPC2019] Jaki Jovsi
[Croatian CPC2019] Jaki Jovsi
题目描述
给定一个长度为 的小写英文字母字符串 ,字符位置从 开始编号。
如果子串 是回文串,则称有序对 为一个回文区间,其中 。回文串是正着读和反着读都相同的字符串。
一个挑战由一个正整数 和 个回文区间 组成,并且满足
也就是说,每个后续区间都严格位于前一个区间的内部,左右端点都必须向内移动。
求不同挑战的总数,对 取模。区间的位置属于挑战的一部分;如果 不同,或某个位置上的区间不同,则视为不同挑战。
输入格式
输入一行一个非空字符串 ,仅由小写英文字母组成,长度不超过 。
输出格式
输出一个整数,表示不同挑战数量对 取模的结果。
样例 1
输入
anadanaokoabanana
输出
65
样例 2
输入
acacacacac
输出
242
样例 3
输入
ananas
输出
18