Result

AC: 2/10, J K
Rank: 441/696
Upsolved: 0/7,

K. number

思路

从右往左扫描字符串
  1. s[i]为'0'时，计数加1("0")。
  2. s[i]='0'且s[i-1]='0'，计数加1("00")，考虑以"00"结尾的子串，和为3的倍数即满足题意。
    设后缀和为sum，[0,i-2]区间内满足sum[j]和sum[i-1]模3同余的左端点j的数量即为合法子串数量。
预处理一下不同后缀和（模3意义下）的数量的后缀和即可。

代码 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
const int MAXN=(int)1e5+10;
char str[MAXN];
int c[MAXN][3],s[MAXN];
//
int main()
{
  scanf("%s",str);
  int n=strlen(str);

  for (int i=n-1;i>=0;i--) {
    s[i]=(s[i+1]+(str[i]-'0'))%3;
    for (int j=0;j<3;j++) {
      c[i][j]=c[i+1][j];
    }
    c[i][s[i]]++;
  }

  ll ans=0;
  for (int i=n-1;i>=0;i--) {
    if (str[i]=='0') {
      ans++;
    }
    if (i-1>=0 && str[i]=='0' && str[i-1]=='0') {
      int k=s[i-1];
      ans+=c[0][k]-c[i-1][k]+1;
    }
  }

  cout<<ans<<endl;

  return 0;
}