题目传送门

解法

对于 \(S_{i}\)，设 \(num_{S_{i}}\) 表示 \(S_{i+1 \sim n}\) 中 \(S_{i}\) 出现的次数，则 \(S_{i}\) 对答案产生的贡献为 \(n-i-num_{S_{i}}\)。

注意原串在存在两个相同的元素的时候，也要统计在内。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll num[30];
char s[1000010];
ll val(char x)
{
    return x-'a'+1;
}
int main()
{
    ll n,ans=0,flag=0,i;
    scanf("%s",s+1);
    n=strlen(s+1);
    for(i=1;i<=n;i++)
    {
        flag|=(num[val(s[i])]!=0);
        num[val(s[i])]++;
    }
    for(i=1;i<=n;i++)
    {
        num[val(s[i])]--;
        ans+=n-i-num[val(s[i])];
    }
    cout<<ans+flag<<endl;
    return 0;
}