题意大概就是给你一个字符串,让你统计所有能被300整除的子串数量
我们很容易就可以看出它一定是以‘00’结尾的子串(暂不考虑单‘0’的情况);
那么对于每一个‘00’,我们只需要统计前面有多少个能被‘3’整除的串,这里就考虑前缀和,设‘00’的位置为i和i+1,如果存在j使1到i的和减去1到j的和为3的倍数,那么a[j]a[j+1]...a[i+1]就是符合的子串
此处还要注意一下要从第0位前缀和为0算起,不然会掉1到i+1为和3的倍数的情况,最后别忘了加上单‘0’的情况哦。
下面是代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
#include<vector>
using namespace std;
#define ll long long
#define maxn 200005
int n,m,k,t;
int s[maxn][3];
char a[maxn];
int now[maxn];
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    ll tot=0,num=0;
    s[0][0]=1;
    for(int i=1;i<n;i++){
        now[i]=(now[i-1]+a[i]-'0')%3;
        s[i][0]=s[i-1][0];
        s[i][1]=s[i-1][1];
        s[i][2]=s[i-1][2];
        s[i][now[i]]++;
    }
    for(int i=1;i<n;i++)
        if(a[i]=='0'&&a[i+1]=='0')
            tot+=s[i-1][now[i]];
    for(int i=1;i<=n;i++)
        if(a[i]=='0')
            tot++;
    printf("%lld\n",tot);
}