xoaso.cpp

#include<iostream>
#include<cstdlib>
#include<vector>

#define long long long
#define nln '\n'

using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    // Input
    //freopen("xoaso.inp", "r", stdin);
    string str;
    getline(cin, str, nln);
    long n = str.size();
    // Process
    str = '$'+str;
    vector<long> sum(n+2, 0), prev_sum(n+2, 0);
    for (long i = 1; i <= n; ++i)
        sum[i] = sum[i-1]+(str[i]-'0');
    for (long i = n; i >= 1; --i)
        prev_sum[i] = prev_sum[i+1] + (str[i]-'0');

    vector<long> rem(3, 0);
    long ans = 0;
    for (long i = 1; i <= n; ++i)
    {
        if (i > 1 && sum[i-1] % 3 == 0)
            ++ans;

        if (prev_sum[i] % 3 == 0)
            ans += rem[0]+1;
        else
            ans += rem[3-prev_sum[i]%3];

        if (i > 1)
            ++rem[sum[i-1]%3];
    }
    cout << ans << nln;
    return 0;
}