被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;
}