Wuwa~做的DP实在是太少了所以开始多练习DP问题了···

被3整除的子序列

被3整除的子序列
题目描述

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

输入描述：

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

输出描述：

输出一个整数

实例：

输入：

123

输出：

3

思路：

一个数字能被3整除，则每位数相加和为3的倍数，我们把每位数字都模上3，处理成0，1，2的样子。

所以我们可以用一个二维数组dp[i][j]来表示前i个长度的数字的所有子序列的和模上3为j的数目 。

对于dp[i][j]我们有以下两种情况：

1. 如果没有用到第i个数字，那么dp[i][j]=dp[i-1][j]；

2. 如果用到了第i个数字，那么dp[i][j]=dp[i-1][(3+j-k)%3]；我们令k的值为第i为数字的值，分别讨论出不同情况的值。

代码：

#include<bits/stdc++.h>

#define debug(x) cout<<"id"<<' '<<x<<endl
using namespace std;

const int N=1e3+10,MOD=1e9+7;
typedef long long LL;

int dp[55][55];  //前i个数字的所有子序列的的和模3为j的个数;

int main(){

    string s;
    cin>>s;

    dp[1][(s[0]-'0')%3]=1;  //第1位数字只有自身一种情况

    for(int i=2;i<=s.size();i++)
    {
        int x=(s[i-1]-'0')%3;   //第i位数字
        for(int j=0;j<=2;j++)   //j为0，1，2的情况
        {
            dp[i][j]=(dp[i-1][j]+dp[i-1][(3+j-x)%3])%MOD;
        }
        dp[i][x]=(dp[i][x]+1)%MOD;   //不要忘了长度为1的数字所构成的子序列
    }

    cout<<dp[s.size()][0]%MOD<<endl;
    return 0;
}