翻转游戏(turn)

首先排除掉长度为\(1\)的子串，还剩个\(\frac{n(n-1)}{2}\)子串，考虑这些子串中哪此子串翻转的结果是相同的，然后去重来计算答案.
注意到一个子串若最左侧和最右侧的字符相同，则这个子串翻转的结果和去掉左右两侧字符的子串翻转的结果时完全相同的，反过来说，就是每对相同的字符实际贡献了一次重复的答案，那么若一种字符出现了\(m\)次，贡献重复答案的次数就是\(\frac{m(m-1)}{2}\)，对每种字符分别去重即可

#include<bits/stdc++.h>
#define MAXN 3000005
#define INF 1e9
using namespace std;

char az[MAXN];
long long tot[27];
long long ans;

int main(){
    // freopen("turn.in", "r", stdin);
    // freopen("turn.out", "w", stdout);
//  freopen(".err", "w", stderr);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);cerr.tie(0);
    
    cin>>az;

    long long l = strlen(az);
    for(long long i=0;i<l;i++){
        tot[az[i]-'a'+1]++;
    }

    for(long long i=1; i<=26; i++){
        ans += tot[i] * (tot[i]-1) / 2;
    }
    
    long long cntt = l * (l-1) / 2 + 1 - ans;
    cout<<cntt<<endl;
    
    return 0;
}