AGC019 B - Reverse and Compare

• 問題

問題概要

文字列Sが与えられる.
1回だけ,Sの i〜j文字目(1<=i<j<=N)だけを反転させることを考える.
文字列は何種類できるか.

解法

重複を含めると,2文字選ぶ組み合わせの数だから,N*(N-1)/2である.
S[i] = S[j]の時,作業(i,j)は(i+1,j-1)と同じであるから,
S[i] = S[j]となる2文字の組み合わせを除けば良い.
j = i+1,i+2の時は(i+1,j-1)の組み合わせは存在しなくなるが,
aa,abaを反転しても元と変わらないので,数えなくて良い.

S[i] = S[j] なる(i,j)の組み合わせの数は,a〜zについて, その出現回数をz(char)とすると,z(char) * (z(char) - 1) /2
で数え上げられる.

メモ

回文関係かと思ったら違った. 考察不足.

@2回目
N(N-1)/2 - (部分文字列の回文の数) でやろうとするミスをした.
xabx で [0,4) と [1,3) の反転は同じだが数えられていないのでダメ.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 202;

int main(){
  string s; cin >> s;
  map<char,ll> mp;
  ll N = s.size();
  rep(i,N){
    if(EXIST(mp,s[i])) mp[s[i]]++;
    else mp[s[i]] = 1;
  }
  ll ans = N * (N-1) / 2 + 1;
  for(char c = 'a'; c <= 'z'; c++) ans -= mp[c]*(mp[c]-1)/2;
  cout << ans << endl;
  return 0;
}