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
#include <array>
#include <unordered_map>
#include <cstdio>

using namespace std;

int main()
{
	auto hasher = [](const pair<int,int> &p) {
		return p.first * 13 + p.second * 17;
	};
	unordered_map<pair<int,int>, int, decltype(hasher)> M(0, hasher);
	array<unordered_map<int, int>, 3> N;

	array<int,3> cnt{};
	long long count = 0;
	int last = -1;
	int last_idx = -1;
	N[0][0] = N[1][0] = N[2][0] = M[{0,0}] = 1;
	for (int length=0; ; length++) {
		char ch = getchar();
		if (ch < 'a' || ch > 'c') break;
		int chi = ch - 'a';
		cnt[chi]++;
		if (chi != last) {
			last = chi;
			last_idx = length;
		}
		count += length-last_idx+1;

		N[chi].clear();

		count += N[0][cnt[2]-cnt[1]];
		N[0][cnt[2]-cnt[1]]++;

		count += N[1][cnt[2]-cnt[0]];
		N[1][cnt[2]-cnt[0]]++;

		count += N[2][cnt[1]-cnt[0]];
		N[2][cnt[1]-cnt[0]]++;

		auto key = make_pair(cnt[1] - cnt[0], cnt[2] - cnt[1]);
		count += M[key];
		M[key]++;
	}
	printf("%lld\n", count);
	return 0;
}