1045I - Palindrome Pairs - CodeForces Solution

/*
 
 File   : Main.cpp
 -------------------
 |   Hello         |
 |   World !       |
 -------------------
 
 */


/* ----------------------------------- DEFINE HERE --------------------------------------*/


#include "bits/stdc++.h"
#include <unordered_map>
using namespace std;
#define mii map<int,int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define pii pair<int,int>
#define endl "\n"
#define sip(s) string s; cin>>s
#define ip(x) int x; cin>>x;
#define inp(x,y) int x,y; cin>>x>>y;
#define iput(a,b,c) int a,b,c; cin>>a>>b>>c
#define input(a,n) for(int i=0;i<n;i++) cin>>a[i]
#define intmax INT_MAX
#define intmin INT_MIN
#define int long long int
#define need_for_speed ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ff(i,a,b) for(int i=a;i<b;i++)
#define rfor(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define forauto(it,arr) for(auto it:arr)
#define prauto(arr) for(auto it:arr) cout<<it<<" "; cout<<"\n";
#define pt(x) { cout<<x<<"\n"; }
#define fs first.second
#define ss second.second
#define pb push_back
#define sc second
#define vpii vector<pii>
#define yesno(ok) cout << (ok ? "YES" : "NO") << '\n';

/* ----------------------------------- GLOBAL'S --------------------------------------*/



/* ----------------------------------- OTHER FUNC'S --------------------------------------*/


/* --------------------------------------- SOLVE -----------------------------------------*/


void solve()
{
    int ans=0;
    // After xor -> 0000 or 000..1...00 -> total 27
    map<int,int> m;
    

    ip(n); vector<pair<string, int>> v;
    ff(i,0,n)
    {
        sip(s); vi cnt(26,0);
        ff(j,0,s.length()) cnt[s[j]-'a'] = (cnt[s[j]-'a']%2 + 1 )%2 ;
        int mask = 0 ;
        ff(j,0,26)
        {
            if(cnt[j]) mask+=(1LL << j);
        }
        
        ans+=m[mask]; // same waale so that 000000..00
        // else kisi ek bit pe diifer karne waale
        for(int flipme=0;flipme<26;flipme++)
        {
            mask^=( 1LL<< flipme );
            ans+=m[mask];
            mask^=( 1LL<< flipme);
        }
        m[mask]++;
    }
    

    
    pt(ans);
    return;
    
}

/* ----------------------------------- MAIN --------------------------------------*/

signed main()
{
    need_for_speed;
    int t=1;
//    cin>>t;
    while (t--)
    {
        solve();
    }
    
}

/* ----------------------------------- SAMPLE TC --------------------------------------
 
 
 
 */




/* ----------------------------------- THINK OF -------------------------------------
 
 BINARY SEARCH !!
 111100000 or 0000001111 -> BS
 dp[N][2] last liya ya nahi ya uska left liya , ya koi ek case liya ( 2 kaam kr skte the us index pe )
 koi range Query ho toh seg tree || 2 pointers
 1 != 1LL So
 
 */