I. Palindrome Pairs

  • Quiz
  • AC
  • 解説
    • たとえばaabとbは同一視できる
    • 各文字の偶奇のみに意味があり、各文字列は26文字をフラグとした整数値として表せる
    • 回文を作れる場合は2パターンあって、偶数長の回文は同じもの同士をくっつけた場合のみ。例：abcとabcをくっつけて回文にする
    • 奇数長の場合は、たとえばabc, abcdをくっつけて回文にできる
      • 他に、abc, bcでもよい
      • 1文字だけ違う文字列ならくっつけて回文にできる
// 各文字の個数の偶奇のみ見て整数にエンコードする
ll f(string& s){
  map<char,ll> mp;
  for(char c : s) mp[c]++;
  ll v = 0;
  rep(i,26){
    char c = 'a'+i;
    ll num = mp[c]%2;
    if(num){
      v += (1LL<<i);
    }
  }
  return v;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    map<ll,ll> mp;

    rep(i,N){
      string s;cin>>s;
      ll v = f(s);
      mp[v]++;
    }

    ll sum=0;

    // 1つ違い (abc & abcd)
    for(auto pa : mp){
      ll v = pa.first;
      ll cnt = pa.second;

      rep(i,26){
        // その文字のみ反転（0->1 or 1->0）したらどうなるか
        // そのbitのxor
        ll w = v ^ (1LL<<i);
        if(mp.count(w)){
          sum += cnt * mp[w];
        }
      }
    }

    sum /= 2;

    // 0つ違い (aab & aab)
    for(auto pa : mp){
      ll cnt = pa.second;
      if(cnt>=2){
        sum += cnt*(cnt-1)/2; // nC2
      }
    }

    p(sum);
    
    return 0;
}