Cod sursa(job #1491492)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 25 septembrie 2015 16:21:43
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int sigma = ('z' - 'a');
const int Nmax = 1000000 + 10;

int T , n , i , j , mask;
int ap[(1<<26)];

ll ans , val , cmmdc;

char sir[Nmax];

ll gcd(ll a , ll b)
{
    ll r = a % b;
    while (r)
    {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int main()
{
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);

    for (scanf("%d\n", &T); T; --T)
    {
        gets(sir+1); n = strlen(sir+1);

        ap[0] = 1; ans = mask = 0;
        for (i =1 ; i<= n; ++i)
        {
            mask ^= (1 << (sir[i] - 'a'));
            ans += ap[mask];
            for (j = 0; j <= sigma; ++j)
                ans += 1LL * ap[mask^(1<<j)];
            ap[mask]++;
        }

        int val = 1LL * n * (n + 1) / 2;
        cmmdc = gcd(ans , val);

        printf("%lld/%lld\n", ans / cmmdc , val / cmmdc);

        memset(ap , 0 , sizeof(ap));
    }

    return 0;
}