被3整除的子序列
链接：https://ac.nowcoder.com/acm/problem/21302
来源：牛客网
题目描述
给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模
答案对1e9+7取模
输入描述:
输入一个字符串，由数字构成，长度小于等于50
输出描述:
输出一个整数
示例2
输出
复制1
#include <bits/stdc++.h> using namespace std; #define ll long long const int mod = 1000000000+7; ll dp[60][5]; int main() { string str; cin>>str; int n =str.length(); for(int i=0;i<n;i++) { dp[i][(str[i]-'0')%3] = 1; } for(int i=1;i<=n-1;i++) { if((str[i]-'0')%3 == 0) { dp[i][0] = 2*dp[i-1][0]+1; dp[i][1] = 2*dp[i-1][1]; dp[i][2] = 2*dp[i-1][2]; } else if((str[i]-'0')%3 == 1) { dp[i][0] = dp[i-1][0]+dp[i-1][2]; dp[i][1] = dp[i-1][1]+dp[i-1][0]+1; dp[i][2] = dp[i-1][2]+dp[i-1][1]; } else{ dp[i][0] = dp[i-1][0]+dp[i-1][1]; dp[i][1] = dp[i-1][1]+dp[i-1][2]; dp[i][2] = dp[i-1][2]+dp[i-1][0]+1; } for(int j=0;j<2;j++) dp[i][j] %= mod; } cout<<dp[n-1][0]<<endl; return 0; }
