被3整除的子序列
被3整除的子序列
https://ac.nowcoder.com/acm/problem/21302
python解答(参考cpp)
s = input()
mod = 1000000007
rows = len(s)
cols = 3
dp = [[0 for c in range(cols)] for r in range(rows)]
m = 0
dp[0][(ord(s[0]) - ord('0'))%3] = 1
for i in range(1, len(s)):
#ord() ASCII码
m = (ord(s[i]) - ord('0'))%3
dp[i][m] = (dp[i][m]+1)%mod
for j in range(3):
dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3])%mod #什么意思没搞懂
print(dp[len(s)-1][0]%mod)
