我的做法是：第一步，设从第 $i$ 位开始，至少到第 $f_i$ 位才能全部消掉，倒着遍历一遍 $i$，根据后面已求出的 $f_j$ 往后跳（$j \gets f_j+1$），直到 $s_i=s_j$ 为止，然后 $f_i \gets j$

第二步，正着遍历一遍，以同样的方式往后跳，将从第 $i$ 位开始能跳的次数记为 $cnt_i$（如果之前跳的时候已经经过了第 $i$ 位则 $cnt_i=0$），答案是 $\sum cnt_i(cnt_i+1)/2$

这个做法能在 $0.01s$ 内正确通过大样例，但不知道在第一步能否构造出数据把复杂度卡到 $O(n^2)$，求大神们帮忙提供 hack 数据或线性复杂度证明，谢谢啦 orz