被3整除的子序列 dp

题目传送门
本文参考资料

注意：子序列可以不连续

/* 设dp[0],dp[1],dp[2],表示除3得到的余数分别为0,1,2。每增加一个数就更新一遍数组。 余数为0：dp[0]=dp[0]+dp[0]+1; 　　　　 dp[1]=dp[1]+dp[1]; 　　　　 dp[2]=dp[2]+dp[2]; 余数为1：dp[0]=dp[0]+dp[2]; 　　　　 dp[1]=dp[1]+dp[0]+1; 　　　　 dp[2]=dp[2]+dp[1]; 余数为2：dp[0]=dp[0]+dp[1]； 　　　　 dp[1]=dp[1]+dp[2]; 　　　　 dp[2]=dp[2]+dp[0]+1; */ 
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int main()
{
   
    int dp[55][4];//dp[i][j]表示到字符串的第i个位置为止，
					//子序列%3余数为j的个数 
	memset(dp,0,sizeof(dp));
	char s[55];
	scanf("%s",s+1);
	int n = strlen(s+1);
	dp[1][(s[1]-'0')%3] = 1; 
	for(int i=2;i<=n;i++)
	{
   
		int m = (s[i]-'0')%3;
		dp[i][m] +=1;
		dp[i][m]%=mod;
		for(int j=0;j<3;j++)
		{
   
			dp[i][j] +=(dp[i-1][j] + dp[i-1][(j+3-m)%3])%mod;//j+3-m由(x+m)%3=j解来 
		}
    }
    cout<<dp[n][0]<<endl;
    return 0;
}