题目来源:：西安电子科技大学第16届程序设计竞赛网络同步赛
dp[i][j]表示以i这一位为最高位，模3等于j的方法数。那么转移就是：t=(j*2+a[i])%3 ,dp[i][t] = dp[i-1][j]; 还有一个转移是只包含第i位的方案所以dp[a[i]]]++;
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
char s[1000007];
ll dp[1000007][3];
int main(){
while(~scanf(" %s",s)) {int len=strlen(s);
memset(dp,0,sizeof(dp));
++dp[0][s[0]-‘0‘];
for(int i=1;i<len;++i){
for(int j=0;j<3;++j){
int t = (2*j%3+s[i]-‘0‘)%3;
dp[i][t]=dp[i-1][j];
}
++dp[i][s[i]-‘0‘];
}
ll ans = 0;
for(int i=0;i<len;++i)ans+=dp[i][0];
printf("%lld\n",ans);
}
}
原文：https://www.cnblogs.com/RRRR-wys/p/8904593.html