被3整除的子序列（线性dp）

链接：https://ac.nowcoder.com/acm/problem/21302?&headNav=acm 来源：牛客网  

时间限制：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: 无限制

dp[i][j]   前i位数能构成mod3为j的子序列的数目

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; typedef long long ll; const int N=55; ll dp[N][3]; char s[N]; int main(){ scanf("%s",s+1); int len=strlen(s+1); ll ans=0; for(int i=1;i<=len;i++){ int a=(s[i]-'0')%3; if(a==0){ dp[i][0]=(dp[i-1][0]+dp[i-1][0]+1)%mod; dp[i][1]=(dp[i-1][1]+dp[i-1][1])%mod; dp[i][2]=(dp[i-1][2]+dp[i-1][2])%mod; } else if(a==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; } else if(a==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][2]+dp[i-1][0]+1)%mod; } } printf("%lld",dp[len][0]); return 0; }