牛客网 被3整除的子序列 区间dp

#include <bits/stdc++.h>
using namespace std;
int mod=1e9+7;
int main()
{
    int dp[55][55][5];//dp[i][j][k]表示在区间(i,j)中被3整除余数为k的个数
    memset(dp,0,sizeof(dp));
    string s;
    cin>>s;
    for(int i=s.length();i>=0;i--) s[i]=s[i-1];
    for(int i=1;i<=s.length();i++){
        dp[i][i][(s[i]-'0')%3]=1;
    }
    for(int i=s.length();i>=1;i--){
        for(int j=i;j<s.length();j++){
            if((s[j+1]-'0')%3==0){
                dp[i][j+1][0]=2*dp[i][j][0]+1;
                dp[i][j+1][1]=2*dp[i][j][1];
                dp[i][j+1][2]=2*dp[i][j][2];
            }
            else if((s[j+1]-'0')%3==1){
                dp[i][j+1][0]=dp[i][j][2]+dp[i][j][0];
                dp[i][j+1][1]=dp[i][j][0]+dp[i][j][1]+1;
                dp[i][j+1][2]=dp[i][j][1]+dp[i][j][2];
            }
            else {
                dp[i][j+1][0]=dp[i][j][0]+dp[i][j][1];
                dp[i][j+1][1]=dp[i][j][1]+dp[i][j][2];
                dp[i][j+1][2]=dp[i][j][2]+dp[i][j][0]+1;
            }
            for(int k=0;k<3;k++) dp[i][j+1][k]=dp[i][j+1][k]%mod;
        }
    }
    /*
    for(int i=1;i<=s.length();i++){
        for(int j=i+1;j<=s.length();j++){
            for(int k=0;k<3;k++){
                cout<<dp[i][j][k]<<' ';
            }
            cout<<endl;
        }
    }
    */
    cout<<dp[1][s.length()][0]<<endl;
    return 0;
}