被3整除的子序列 动态规划

   简单说下题意，给定一个数字串，问有多少的子串可以被3整除。

   首先一个数如果可以被3整除，那么这个数各位和一定可以被3整除。所以这个题应该是线性dp，我们定义dp[i][j]为前i个中整除3余数为j（只有0，1，2三个数）的个数，然后从头到尾线性dp一遍就可以了。

   下面看一下代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
    string t;
    cin>>t;
    int len=t.length();
    int dp[55][3];
    memset(dp,0,sizeof(dp));
    int m=0;
    dp[0][(t[0]-'0')%3]=1;
    for(int i=1;i<len;i++){
        m=(t[i]-'0')%3;
        dp[i][m]=(dp[i][m]+1)%mod;
        for(int j=0;j<3;j++){
            dp[i][j]+=(dp[i-1][j]+dp[i-1][(j+3-m)%3])%mod;
        }
        //dp[i][m]=(dp[i][m]+1)%mod;
    }
    /*for(int q=0;q<len;q++){
        for(int w=0;w<3;w++){
            cout<<dp[q][w]<<" ";
        }
        cout<<endl;
    }*/
    cout<<dp[len-1][0]%mod<<endl;
    return 0;
}