1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    string s;
    cin >> s;
    const int n = (int)size(s);
    vector<int> a(n + 1), b(n + 1), c(n + 1);
    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'a') a[i]++;
        if (s[i - 1] == 'b') b[i]++;
        if (s[i - 1] == 'c') c[i]++;
        a[i] += a[i - 1];
        b[i] += b[i - 1];
        c[i] += c[i - 1];
    }
    {
        map<pair<int, int>, int> cnt;
        cnt[{0, 0}]++;
        for (int i = 1; i <= n; i++) {
            answer += cnt[{a[i] - b[i], a[i] - c[i]}];
            cnt[{a[i] - b[i], a[i] - c[i]}]++;
        }
    }
    {
        for (auto c1 : {'a', 'b', 'c'}) {
            for (auto c2 : {'a', 'b', 'c'}) {
                if (c1 >= c2) continue;
                map<pair<int, int>, int> cnt;
                cnt[{0, 0}]++;
                for (int i = 1; i <= n; i++) {
                    int cnt1, cnt2;
                    if (c1 == 'a')
                        cnt1 = a[i];
                    else if (c1 == 'b')
                        cnt1 = b[i];
                    else
                        cnt1 = c[i];
                    if (c2 == 'a')
                        cnt2 = a[i];
                    else if (c2 == 'b')
                        cnt2 = b[i];
                    else
                        cnt2 = c[i];
                    answer += cnt[{cnt1, cnt2}];
                    cnt[{cnt1, cnt2}]++;
                }
            }
        }
    }
    {
        {
            map<pair<int, int>, int> cnta, cntb, cntc;
            cnta[{0, 0}]++;
            cntb[{0, 0}]++;
            cntc[{0, 0}]++;
            for (int i = 1; i <= n; i++) {
                int c1 = b[i] - c[i];
                int c2 = a[i] - c[i];
                int c3 = a[i] - b[i];
                answer += cnta[{a[i], c1}];
                answer += cntb[{b[i], c2}];
                answer += cntc[{c[i], c3}];
                cnta[{a[i], c1}]++;
                cntb[{b[i], c2}]++;
                cntc[{c[i], c3}]++;
            }
        }
    }
    cout << answer << '\n';
}