区间dp

因为是子序列，所以可以不连续，因此需要保存每个区间上余数为0，1，2的数目 用dp[i][k] 表示从0到i区间上，余数为k的数目 因为每次区间扩张一个数时，如果这个数的对3的余数为1，那么只要这个新的数结合上上一个区间余数为2的数列，新的子序列的余数就是0了，
别忘了还有原先子序列本来余数就是0的数，对于这些数来讲，不需要加上新来的数，因此直接继承即可。
也就是 dp[i][0]=dp[i-1][0]+dp[i-1][2];
同样的，dp[i][1]=dp[i-1][1]+dp[i-1][0]+1;
只要0~i-1区间上余数为0的数列，加上新来的第i个数后，就是余数为1了。另外因为新的数本身就是余数为1，它自己就能构成只有它自己的子序列，所以需要加1。另外还加上原来余数就为1的数。
那么同理，dp[i][2]=dp[i-1][1]+dp[i-1][2].

另外还需讨论新的数余数为0，2的情况。不再赘述。
代码：

	#include<iostream>
#include<string>
using namespace std;



	long long mod=1e9+7;
long long dp[55][5];   //从0到j区间上，余数为k的数目



	int main()
{
 string num;
 cin>>num;
 int n=num.length();
 
 for(int i=0;i<n;i++)
 {
  dp[i][(num[i]-'0')%3]=1;
 }
 
 for(int i=1;i<=n-1;i++)
 {
  if((num[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((num[i]-'0')%3==1)
  {
   dp[i][0]=dp[i-1][0]+dp[i-1][2];
   dp[i][1]=dp[i-1][0]+dp[i-1][1]+1;
   dp[i][2]=dp[i-1][1]+dp[i-1][2];
  }
  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]+1+dp[i-1][0];
  }
  
  for(int j=0;j<3;j++) dp[i][j]%=mod;
 }
 
 cout<<dp[n-1][0];
 }