题目链接
1、dp变量
dp[len][m] 表示前len长度中,子序列各位和对3求余为m的子序列数量
2 递推公式,
1、当 (s[i] - '0') % 3 == 0时 dp[i][0] = dp[i - 1][0] + dp[i -1][0] + 1
dp[i][1] = dp[i - 1][1] + dp[i -1][0]
dp[i][2] = dp[i - 1][2] + dp[i -1][0]
2、 当 (s[i] - '0') % 3 == 1时 dp[i][1] = dp[i - 1][1] + dp[i -1][0] + 1
dp[i][0] = dp[i - 1][0] + dp[i -1][2]
dp[i][2] = dp[i - 1][2] + dp[i -1][1]
3、当 (s[i] - '0') % 3 == 2时 dp[i][2] = dp[i - 1][2] + dp[i -1][0] + 1
dp[i][0] = dp[i - 1][0] + dp[i -1][1]
dp[i][1] = dp[i - 1][1] + dp[i -1][2]
3
初始值:(以0为第一个元素位置)
dp[0][(s[0] - '0') % 3] = 1;
代码
/* dp[len][m]; 前len长度中,和对3求余的子序列数量 */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 LL; const int maxn = 1000 + 5; const int mod = 1e9 + 7; int dp[55][3]; int Dp(int len,const string &s) { memset(dp,0,sizeof dp); dp[0][(s[0] - '0') % 3] = 1; for(int i = 1; i < len; i++){ int m = (s[i] - '0') % 3; dp[i][m]++;//单独一个也算一个子序列 for(int j = 0; j < 3; j++){ dp[i][j] += (dp[i - 1][j] + dp[i - 1][(j + 3 - m) % 3]) % mod; } } return dp[len - 1][0]; } int main() { std::ios::sync_with_stdio(false); string s; cin>>s; int len = s.size(); int ans = Dp(len,s) % mod; cout<<ans<<endl; return 0; }