链接：https://ac.nowcoder.com/acm/problem/21302
来源：牛客网
被3整除的子序列

题目描述

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

输入描述:

输入一个字符串，由数字构成，长度小于等于50

输出描述:

输出一个整数

输入


 
132　
123456
　

输出

3

23

思路


题意很明确，但是还是有一点模糊的在于子串和子序列的区别，子序列不要求连续。对于这道题，直接使用区间dp，但是需要记录下区间内3个数据，即区间内被3除余数为0，1，2的子序列的个数。
对于区间的扩展，需要对这三个数进行更新，更新还是看代码吧。需要注意的是每算一个区间的数据需要取模。


代码

#include <bits/stdc++.h>
using namespace std;
int mod=1e9+7;
int main()
{
    int dp[55][55][5];//dp[i][j][k]表示在区间(i,j)中被3整除余数为k的个数
    memset(dp,0,sizeof(dp));
    string s;
    cin>>s;
    for(int i=s.length();i>=0;i--) s[i]=s[i-1];
    for(int i=1;i<=s.length();i++){
        dp[i][i][(s[i]-'0')%3]=1;
    }
    for(int i=s.length();i>=1;i--){
        for(int j=i;j<s.length();j++){
            if((s[j+1]-'0')%3==0){
                dp[i][j+1][0]=2*dp[i][j][0]+1;
                dp[i][j+1][1]=2*dp[i][j][1];
                dp[i][j+1][2]=2*dp[i][j][2];
            }
            else if((s[j+1]-'0')%3==1){
                dp[i][j+1][0]=dp[i][j][2]+dp[i][j][0];
                dp[i][j+1][1]=dp[i][j][0]+dp[i][j][1]+1;
                dp[i][j+1][2]=dp[i][j][1]+dp[i][j][2];
            }
            else {
                dp[i][j+1][0]=dp[i][j][0]+dp[i][j][1];
                dp[i][j+1][1]=dp[i][j][1]+dp[i][j][2];
                dp[i][j+1][2]=dp[i][j][2]+dp[i][j][0]+1;
            }
            for(int k=0;k<3;k++) dp[i][j+1][k]=dp[i][j+1][k]%mod;
        }
    }
    /*
    for(int i=1;i<=s.length();i++){
        for(int j=i+1;j<=s.length();j++){
            for(int k=0;k<3;k++){
                cout<<dp[i][j][k]<<' ';
            }
            cout<<endl;
        }
    }
    */
    cout<<dp[1][s.length()][0]<<endl;
    return 0;
}