1.牛客题号:NC21302

2.题目原文:

• 给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除答案对1e9+7取模

3.牛客链接:https://ac.nowcoder.com/acm/problem/21302

4.基本思路:线性dp

5.代码：

using namespace std;
typedef long long ll;
const int p = 1e9+7;
string s;
ll ans;
int n;
int a[51];
ll dp[51][3];
/*void dfs(int dep,int cnt)
{
    if(dep==n)
    {
        if(cnt%3==0&&cnt!=0) ans=(ans+1)%p;
        return;
    }
    dfs(dep+1,cnt+s[dep]-'0');
    dfs(dep+1,cnt);
}*/
int main()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    for(int i=1;i<=n;i++) a[i]=(s[i]-'0')%3;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=2;j++)
        {
            dp[i][j]+=dp[i-1][j]+(dp[i-1][(j-a[i]+3)%3]);
            dp[i][j]%=p;
        }
    }
    cout<<dp[n][0]-1;
    return 0;
}