0%

牛客 21302 被3整除的子序列 (动态规划、Python)

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld
链接:https://ac.nowcoder.com/acm/problem/21302
来源:牛客网

题目描述

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

输入描述:

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

输出描述:

输出一个整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
示例1
输入
132
输出
3

示例2
输入
9
输出
1

示例3
输入
333
输出
7

示例4
输入
123456
输出
23

示例5
输入
00
输出
3

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

动态转移方程为:

dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % mod

1
2
3
4
5
6
7
8
9
10
s = input()

mod = 1000000007
dp = [[0] * 3 for _ in range (51)]
for i in range (1, len(s)+1):
m = int(s[i-1])%3
dp[i][m] = 1
for j in range (3):
dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % mod
print(dp[len(s)][0])
-------------    本文结束  感谢您的阅读    -------------