众所周知,在算法竞赛中,出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个简单题,没想到却出成了重坑细节题;本想出个中等难度题,结果却变成了防AK题。因此,为了让一场比赛能有良好的体验,有一个靠谱的验题人是非常重要的。
CC出好题目后,便拿给小马哥看。不出所料,这些题目小马哥全都是看一眼就会做,但他觉得这对于参赛选手来说还是有点难。为了避免CC被喷成毒瘤出题人,小马哥准备加一道签到题。
小马哥有一个只由小写字母组成的字符串S,他会问你一些关于这个字符串的问题。小马哥每次提问时会给你一个整数i,意思是要把字符串S在第i和第i+1个字符之间切断,这样便得到两个新串S[1,i]及S[i+1,|S|]。记A=S[1,i],B=S[i+1,|S|]。现在,先考虑A的所有连续子串,再考虑B的所有连续子串,小马哥问你A,B之间相同子串对有多少个。
也就是说,小马哥想让你计算下面这个式子:
其中,求和式右边的式子是这样一个函数:
你能解决小马哥的问题,并签到成功吗?