#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; }
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; } |