被3整除的子序列（简单dp）

比眉伴天荒 2023-07-04 12:56 19阅读 0赞

# 链接：[https://ac.nowcoder.com/acm/problem/21302][https_ac.nowcoder.com_acm_problem_21302] #

--------------------

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
    空间限制：C/C++ 524288K，其他语言1048576K
    64bit IO Format: %lld

## 题目描述 ##

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

## 输入描述: ##

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

## 输出描述: ##

输出一个整数
    示例1
    输入
    复制
    132
    输出
    复制
    3
    示例2
    输入
    复制
    9
    输出
    复制
    1
    示例3
    输入
    复制
    333
    输出
    复制
    7
    示例4
    输入
    复制
    123456
    输出
    复制
    23
    示例5
    输入
    复制
    00
    输出
    复制
    3

## 备注: ##

n为长度
    子任务1: n <= 5
    子任务2: n <= 20
    子任务3: 无限制

--------------------

## 思路： ##

一个数字能够被3整除的条件：数字各位和能够整除3
    设dp[i][j]位前i位和为j,
    ## 那么包含前面的选择，对于第j位有选与不选两种决策：
    第j位为数字num;
    选：dp[i][j] += dp[i-1][j-num];
    不选：dp[i][j]  = dp[i-1][j];
    对于选的情况是：加上num恰巧等于j，即原来是j-num，
    （j-num可能为负数，此时要加上余数再取余）
    和能够整除3，那么 各位数字和 %3有：0 1 2三种取值
    所以有：
    num = num % 3；
    选：dp[i][j] = dp[i-1][(j-num + 3)%3];
    不选：dp[i][j]  = dp[i-1][j];
    
    ## 不包含前面的选择，即对num本身
    对于num，它本身也要算上

--------------------

## AC代码： ##

#include <bits/stdc++.h>
    using namespace std;
    const int mod = 1e9+7;
    int dp[55][5];
    int main()
    {
        
        char s[55];
        cin>>(s+1);
        int len = strlen(s+1);
        for(int i = 1; i <= len; i++)
        {
        
            int num = (s[i] - '0') % 3;
            for(int j = 0; j <= 2; j++)
            {
        
                dp[i][j] = (dp[i-1][j] + dp[i-1][(j-num+3)%3])%mod;
            }
            //num本身
            dp[i][num] = (dp[i][num] + 1) % mod;
        }
        cout<<dp[len][0]<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_problem_21302]: https://ac.nowcoder.com/acm/problem/21302