鏈接：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: 無限制
字符串最長是50，所以整個字符串每個數位最大值加和就是450.所以我們可以枚舉數位的加和。
dp[i][j]代表著前i位，加值和為j的子序列的個數。
狀態轉移方程為：首先令dp[i][j]=dp[i-1][j]
如果當前位值為x并且x==j，那么dp[i][j]++;這代表著這一位所做的貢獻。
如果當前位值為x并且x>=j，那么dp[i][j]+=dp[i-1][j-x];代表著這一位與之前的每個數位合起來整體的貢獻。
代碼如下：

#include<bits/stdc++.h> #define mod 1000000007 #define ll long long using namespace std;const int maxx=51; int dp[maxx][455]; string s;int main() {while(cin>>s){int len=s.length();memset(dp,0,sizeof(dp));dp[0][s[0]-'0']++;for(int i=1;i<len;i++){for(int j=0;j<451;j++){dp[i][j]=dp[i-1][j];if(s[i]-'0'==j) dp[i][j]++;if(j>=s[i]-'0') dp[i][j]+=dp[i-1][j-(s[i]-'0')];dp[i][j]%=mod;}}ll ans=0;for(int i=0;i<451;i++) if(i%3==0) ans=(ans+dp[len-1][i])%mod;cout<<ans<<endl;} }

今天吃飯突然想起另一種做法。
我們之前是枚舉的前面加值和，那么我們也可以枚舉余數的。畢竟這個題目數據量小可以枚舉加值和，但是遇到數據量大的就不行了。我們枚舉余數，其實和枚舉加值和的相差無異。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std;const int maxx=51; int dp[maxx][5]; string s;int main() {int len,x;while(cin>>s){len=s.length();memset(dp,0,sizeof(dp));dp[0][(s[0]-'0')%3]=1;for(int i=1;i<len;i++){x=(s[i]-'0')%3;dp[i][x]++;for(int j=0;j<3;j++){dp[i][j]+=(dp[i-1][j]+dp[i-1][(3+j-x)%3])%mod;//我們在這里主要是看x對之前值的貢獻，假設我們設一個m，使得（x+m）%3==j，那么x對于這個m就有貢獻了。那么m=3*k+j-x（k是商），但是所有的數字都不超過6，但是都大于3，所以k就是1了。}}printf("%lld\n",dp[len-1][0]);} }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的被3整除的子序列（线性dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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