题意：
输入一个只包含数字的字符串，求出是300的倍数的子串的个数（不同位置的0、00、000等都算，并考虑前导零的情况）。
sample input：
600
123000321013200987000789
sample output：
4
55
题解：
O(n)做法：遍历一遍，求前缀和sum取余3，统计sum的个数num[sum],遇到本位和下一位都是0，则把之前统计的个数加上，最后加上单独0的个数。
O(300n)DP做法：如下
官方题解：
Code：
O(n)做法如下：
/*6ms*/
1 #include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int M=1e5+;
char s[M];
int main()
{
while(~scanf("%s",s+))
{
int len=strlen(s+),sum=,num[]={};
ll cnt=;
num[]=;
for(int i=;i<=len;i++){
sum=(sum+(s[i]-''))%;
if(s[i]==''&&s[i+]==''){
cnt+=num[sum];
}
if(s[i]=='')cnt++;
num[sum]++;
}
printf("%lld\n",cnt);
}
return ;
}
DP做法如下【O(300n)】：
/*224ms*/
1 #include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int M=1e5+;
char s[M];
int dp[M][];
int main()
{
while(~scanf("%s",s+))
{
memset(dp,,sizeof(dp));
dp[][s[]-'']=;
int len=strlen(s+);
for(int i=;i<=len;i++){
dp[i][s[i]-'']++;
for(int j=;j<;j++){
int flag=(j*+s[i]-'')%;
dp[i][flag]+=dp[i-][j];
}
}
ll ans=;
for(int i=;i<=len;i++)
ans+=dp[i][];
printf("%lld\n",ans);
}
return ;
}
