题目内容

塔子哥最近迷上了字符串，并且认为一个字符串的美好值为字符串内，连续相同子串的数量。例如“aabbccddef”的美好值为6。

塔子哥的朋友给了他一个01串，已经迷恋上字符串的塔子哥想知道，这个01串所有子串的美好值之和是多少？

思路：数学优化

暴力做法

一个最朴素的方法：枚举每个区间（$C(n,2)$个 ），计算区间中极长段的个数。 时间复杂度$O(n^2)$ ， $n = 1e5 , n^2 = 1e10 > 1e8$ , 超时。

数学优化:贡献法

考虑原串其中的某一个极长段对总体答案的贡献: