输入样例：

ababc

输出样例：

28

解题思路

分析

该题如果暴力枚举则是一个$O(n^2)$的复杂度
很显然当n到10000时测评就很难通过
那么我们就要考虑一下有什么方法可以优化到$O(nlogn)$,$O(n)$以内

举例

按样例的列举如下图划分，我们就可以将本题转换成一个计算每个字符贡献的情况
①先举一个没有重复的例子，他的每个字母出现的次数
s[i]:a　　b　　c　　d　　e
f[i]:5　　8　　9　　8　　5
有没有看出什么，没有？那我们再细分
　1*5　2*4　3*3　4*2　5*1
是不是看出了些什么(#^.^#)

②再来看一个有重复了例子
s[i]:a　　b　　a　　b　　c
f[i]:5　　8　　6　　4　　5
如下图所示第3个位置a出现了三段，与一段与第1个位置a发生了重复(舍去[ f[i] * 1/3 ])
如下图所示第4个位置b出现了四段，与两段与第2个位置b发生了重复(舍去[ f[i] * 2/4 ])

那么我么只需开一个数组last[]记录上一个字母s[i]出现的最后位置即可知道多少位置发生重复
重复a　　　　3:(9-9*1/3)
重复b　　　　　　4:(8-8*2/4)

推公式

重复s[i]： f[i] - f[i] / i*last[s[i]]

样例解释

子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3

 b    1
 ba   2
 bab  2
 babc 3

  a   1
  ab  2
  abc 3

   b  1
   bc 2

    c 1

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
char s[N];
ll f[N];    //预处理会爆int
int last[30];
int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    ll ans = 0;
    //预处理没有任何重复的情况；
    for(int i=1;i<=n-i+1;i++)f[i] = f[n-i+1] = (n-i+1)*(ll)i; //注意乘的时候一定要转long long
    //统计总贡献，并去重
    for(int i = 1;i<=n;i++){
        int t = s[i]-'a';
        if(!last[t]){    //判断有无重复部分
            ans += f[i];
        }else{
            ans += f[i] - f[i]/i*last[t]; //减去重复部分；
        }
        last[t] = i; //记录当前字母最后出现位置
    }
    printf("%lld",ans);
    return 0;
}