[nowcoder] 21302 被3整除的子序列（动态规划）

[nowcoder] 21302 被3整除的子序列

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

给你一个长度为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: 无限制

题解

思路

由于是子序列，因此不一定连续。所以应当注意这样一个事实，当前位的状态有3种，分别是当前位数字除3余0，除3余1，除3余2三种情况。定义状态转移(dp[i][j],j=0,1,2。(dp[i][0],dp[i][1],dp[i][2]))，3种状态表示对于第(i)位数字，之前的能组成的余数为(j)的序列数目。对于第(i)位数字，有下面三种情况：

(MOD 3 = 0)
此情况下，相当于不改变之间子序列的状态，仅仅是在(MOD3=0)这种状态下需要+1.

[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]\ ]

(MOD 3 = 1)
此情况下，相当于原来状态不变或者，改变一种状态，即：

[dp[i][0] = dp[i-1][0]+dp[i-1][2]\ dp[i][1] = dp[i-1][0]+dp[i-1][1]+1\ dp[i][2] = dp[i-1][2]+dp[i-1][1]\ ]

(MOD 3 = 2)
此情况下，相当于原来状态不变或者，改变一种状态，即：

[dp[i][0] = dp[i-1][0]+dp[i-1][1]\ dp[i][1] = dp[i-1][2]+dp[i-1][1]\ dp[i][2] = dp[i-1][2]+dp[i-1][0]+1\ ]

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

const int MAXN = 50+10;
char str[MAXN];
const ll MOD = 1e9+7;
int dp[MAXN][3];

void init(){
	memset(dp,0,sizeof(dp));
		
}

int main(){
	while(~scanf("%s",str)){
		init();
		int len = strlen(str);
		for(int i=0;i<len;i++){
			dp[i][(str[i]-'0')%3]=1;
		}
		for(int i=1;i<len;i++){
			int th = str[i]-'0';
			if(th%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(th%3==1){
				dp[i][0] = dp[i-1][0]+dp[i-1][2];
				dp[i][1] = dp[i-1][0]+dp[i-1][1]+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][2]+dp[i-1][1];
				dp[i][2] = dp[i-1][2]+dp[i-1][0]+1;
			}
			for(int j=0;j<3;j++) dp[i][j]%=MOD;
		}
		printf("%d
",dp[len-1][0]);
		
		memset(str,0,sizeof(str));
	}
	
	return 0;
}