同個人網站 https://www.serendipper-x.cn/，歡迎訪問 ！

時間限制：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 輸入 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

s = input()mod = 1000000007 dp = [[0] * 3 for _ in range (51)] for i in range (1, len(s)+1):m = int(s[i-1])%3dp[i][m] = 1for j in range (3):dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % mod print(dp[len(s)][0])

總結

以上是生活随笔為你收集整理的牛客 21302 被3整除的子序列 （动态规划、Python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。