#P11350. 在四方城外

    ID: 10341 传统题 1000ms 512MiB 尝试: 4 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-KMP字符串周期快速幂等比数列求和等差数列求和border相关

在四方城外

题目背景

柳花、青山与月光。

诗中的酒香与诗外的酒香。

城中的天空与城外的天空。

一字一句,一笔一划,所知晓的,尚懵懂的。

看呀看,学呀学,世界正如浊酒,滋味饮酌方知。

题目描述

定义字符串 SS 的扩展操作为:

  • 求出 SS 的最长 border\text{border} TT。

  • S′←S+TS'\leftarrow S+T。

注意,本题的 border\text{border} 指真 border\text{border}(即字符串本身不计入 border\text{border})。

设扩展操作的权值为扩展后字符串的长度 ∣S′∣|S'|,请求出字符串 SS 第 LL 次扩展到第 RR 次扩展的权值之和。

由于结果可能很大,请输出答案对 998244353998244353 取模的结果。

输入格式

第一行一个仅由小写字母构成的字符串 SS。

第二行两个整数 L,RL,R。

输出格式

输出为一个数,即答案对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

ababcab
1 3

输出 #1

39

输入输出样例 #2

输入 #2

aa
3 5

输出 #2

59

说明/提示

样例一解释

第 11 次扩展操作:ababcab[ab],权值为 99。

第 22 次扩展操作:ababcabab[abab],权值为 1313。

第 33 次扩展操作:ababcabababab[abab],权值为 1717。

权值之和为 9+13+17=399+13+17=39。

数据范围与约束

子任务 1(15 分):borderS=0\text{border}_{S} = 0。

子任务 2(25 分):borderS=∣S∣−1\text{border}_{S} = |S|-1。

子任务 3(60 分):无特殊性质。

对于 100%100\% 的数据,1≤∣S∣≤106,1≤L≤R≤1091 \le |S| \le 10^6,1 \le L \le R \le 10^9,输入均为整数和小写字母。