2019牛客暑期多校训练营（第四场）
Result
AC: 2/10, J KRank: 441/696
Upsolved: 0/7,
K. number
思路
从右往左扫描字符串
- s[i]为'0'时，计数加1("0")。
- 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;
}
