题目是DP，所以看完题目就想着找递推式

一.首先dp数组表示什么，一开始看完有两种想法：

  1. dp[i]表示长度为i的满足子序列（为了表达简单，满足被三整除的子序列简称为满足子序列）个数
  2. dp[i]表示主串中前i个元素可以构成的所有子序列

二. 然后开始找递推关系 不论是1还是2，它们的递推都是在一个字串上添加上一个元素，所以要先搞清楚添加一个元素后前后的数值变化，来建立递推关系 首先有两个性质：

  1. 对于3的倍数（可以被三整除的数）其各个位上数字之和为3的倍数
  2. 当两个数相加取余时满足分配律(这里表达可能有点问题)。即对整数a、b,若a%3=m,b%3=n;那么则(a+b)%3=（a%3+b%3）%3=(m+n)%3;

根据性质1，我们添加一个元素a后是否为三的倍数，只用看+a后是否为3的倍数

而+a后是否为3的倍数，就可以用性质2来连接前后了

即+a后是否为3的倍数，只用看a%3+b%3(假设原本字串和为b)%3是否为0了，

那么就只有三种情况: 1.a%3==0且b%3==0; 2.a%3==1且b%3==2; 3a%3==2且b%3==1; 这样就建立了前后的递推关系 代码如下：

#include<bits/stdc++.h>
using  namespace std;
int main(void)
{
    char s[50+2];
    cin>>s;
    int len=strlen(s);
    long long dp[50+2][3];//dp[i][j]表示含前i个数字的子序列可以被三整除余j的个数
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;
    for(int i=0;i<len;i++)
    {
    //注意要同时记录%3==1,%3==2的个数
      if((s[i]-'0')%3==0)
      {
          dp[i+1][0]=dp[i][0]+dp[i][0]+1;
          dp[i+1][1]=dp[i][1]+dp[i][1];
          dp[i+1][2]=dp[i][2]+dp[i][2];
      }
      else if((s[i]-'0')%3==1)
      {
          dp[i+1][0]=dp[i][0]+dp[i][2];
          dp[i+1][1]=dp[i][1]+dp[i][0]+1;
          dp[i+1][2]=dp[i][2]+dp[i][1];
      }
      else if((s[i]-'0')%3==2)
      {
          dp[i+1][0]=dp[i][0]+dp[i][1];
          dp[i+1][1]=dp[i][1]+dp[i][2];
          dp[i+1][2]=dp[i][2]+dp[i][0]+1;
      }
    }
    int mod=1e9+7;
    cout<<dp[len][0]%mod;
    return 0;
}