被3整除的子序列

#include <bits/stdc++.h> using namespace std; #define ll long long const int mod = 1000000000+7;
ll dp[60][5]; int main()
{ string str;
    cin>>str; int n =str.length(); for(int i=0;i<n;i++)
    {
        dp[i][(str[i]-'0')%3] = 1;
    } for(int i=1;i<=n-1;i++)
    { if((str[i]-'0')%3 == 0)
        {
            dp[i][0] = 2*dp[i-1][0]+1;
            dp[i][1] = 2*dp[i-1][1];
            dp[i][2] = 2*dp[i-1][2];
        } else if((str[i]-'0')%3 == 1)
        {
            dp[i][0] = dp[i-1][0]+dp[i-1][2];
            dp[i][1] = dp[i-1][1]+dp[i-1][0]+1;
            dp[i][2] = dp[i-1][2]+dp[i-1][1];
        } else{
            dp[i][0] = dp[i-1][0]+dp[i-1][1];
            dp[i][1] = dp[i-1][1]+dp[i-1][2];
            dp[i][2] = dp[i-1][2]+dp[i-1][0]+1;
        } for(int j=0;j<2;j++)
            dp[i][j] %= mod;
    }
    cout<<dp[n-1][0]<<endl; return 0;
}