被3整除的子序列

网址为：被3整除的子序列 (nowcoder.com)

题目描述

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模

输入描述:

输入一个字符串，由数字构成，长度小于等于50

输出描述:

输出一个整数

示例1

输入

复制132

132

输出

复制3

3

示例2

输入

复制9

9

输出

复制1

1

示例3

输入

复制333

333

输出

复制7

7

示例4

输入

复制123456

123456

输出

复制23

23

示例5

输入

复制00

00

输出

复制3

3

备注:

n为长度
子任务1: n <= 5
子任务2: n <= 20
子任务3: 无限制

动态规划问题，可将其分成子状态：第n位的数字mod3等于0，1，2时。可以表示为dp[i][0],dp[i][1],dp[i][2],i表示为第i位。
则可以推出：
1.n%3 == 0时,i位等于前i-1位mod3 ==0的子序列个数加上当前i位后多出来的子序列个数加上n本身也是一个mod3 ==0的子序列,表达式如下：
dp[i][0] = dp[i - 1][0] + dp[i - 1][0] + 1
dp[i][1] = dp[i -1][1] + dp[i - 1][1]
dp[i][2] = dp[i - 1][2] + dp[i -1][2]

2.n%3 == 1时,前i-1位mod3==2的子序列后面添加一位mod3 ==1的数就可以整除3，比如2mod3=2，21mod3=0
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]

3.n%3==2时，
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//加一是因为它本身也是一种情况
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\\n'
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int N = 1e5+10;
int dp[55][5];
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
void solve()
{string s;cin>>s;int len=s.size();s=" "+s;for(int i=1;i<=len;i++){if((s[i]-'0')%3==0){dp[i][0]=(2*dp[i-1][0]+1)%mod;dp[i][1]=(2*dp[i-1][1])%mod;dp[i][2]=(2*dp[i-1][2])%mod;}else if((s[i]-'0')%3==2){dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;dp[i][1]=(dp[i-1][1]+dp[i-1][2])%mod;dp[i][2]=(dp[i-1][0]+dp[i-1][2]+1)%mod;}else if((s[i]-'0')%3==1){dp[i][0]=(dp[i-1][0]+dp[i-1][2])%mod;dp[i][1]=(dp[i-1][1]+dp[i-1][0]+1)%mod;dp[i][2]=(dp[i-1][2]+dp[i-1][1])%mod;}}cout<<dp[len][0]<<endl;
} 
signed main()
{int t;t=1;while(t--){solve();}
}

仔细观察发现dp[i][]只与dp[i - 1][]有关系,那么我们可以考虑用变量记录前一位的三个状态，从而降低空间复杂度，从二维变成一维

#include<bits/stdc++.h>
using namespace std;const int mod = 1e9+7;int main(){string str;cin >> str;int len = str.size();int num[len + 5];for(int i = 1;i <= len; ++i){num[i] = str[i - 1] - '0';} int dp[5]={0},one = 0,two = 0,zero = 0;for(int i = 1;i <= len; ++i){if(num[i] % 3 == 0){dp[0]=(2 * zero + 1) % mod;dp[1]=(2 * one) % mod;dp[2]=(2 * two) % mod; }else if(num[i] % 3 == 1){dp[0]=(zero + two) % mod;dp[1]=(one + zero + 1) % mod;dp[2]=(two + one) % mod;}else if(num[i] % 3 == 2){dp[0] = (zero + one) % mod;dp[1] = (one + two) % mod;dp[2] = (two + zero + 1) % mod;}zero = dp[0];one = dp[1];two = dp[2];}cout << dp[0] << '\\n';return 0;
}