「AGC019B」 Reverse and Compare

题意

给定一个长度为 \(n\) 小写英文字母组成的字符串 \(s\)。可以任意选定 \(1\le x\le y\le n\)，把 \(s_x\) 到 \(s_y\) 之间的字符翻转。 求最终不同字符串的方案数。

分析

我们先考虑所有字符都不同的情况。

小学奥数的加法原理告诉我们，每一位都不同的字符串，对于第 \(i\) 位，可以增加 \(i-1\) 种翻转方案。

再考虑加入相同的情况。

如 \(s=abcad\)，若翻转 \([1,4]\)，和翻转 \([2,3]\) 等效。同理，每一组相同字符都要给答案减一。

用一个桶记录每种字母出现次数，总时间复杂度 \(O(|s|)\)。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
string s;
ll n,sum[200],ans=1;
signed main(){
    cin>>s;
    n=s.size();
    for(ll i=0;i<n;++i){
        ++sum[s[i]];
        ans+=i+1-sum[s[i]];
    }
    printf("%lld",ans);
}