被3整除的子序列 题目描述 给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除 答案对1e9+7取模 输入描述: 输入一个字符串，由数字构成，长度小于等于50 输出描述: 输出一个整数 输入 132 输出 3

### 回答1：
这是一个关于去除子序列中包含数字3的题目。给你一个长度为50的数字串，问你有多少个子序列构成的数字串可以被3整除。答案为1e9+7取模。 输入描述: 输入一个字符串，由0-9组成，长度小于等于50。
输出描述: 输出一个整数，表示答案。 输入一个长度为50的数字字符串，由数字组成。让你输出里面去掉子序列包含数字3的数字串的长度。举个例子，输入132，因为包含3，所以去掉{3,13,32,132}四个子序列，去掉后只剩下1个子序列2，所以输出3。

### 回答2：
本题可以使用动态规划的思路来解决。我们可以使用一个二维数组dp[i][j]表示以第i个数字结尾的长度为j的子序列能否被3整除，其中i的范围是1到50，j的范围是1到50。dp[i][j]的值为0或1，0表示不能被3整除，1表示能被3整除。

对于dp[i][j]，我们可以通过dp[i-1][j-1]或dp[i-1][j]来转移。如果dp[i-1][j-1]为1，则说明在前面的j-1个数字中有一个子序列能被3整除，此时如果第i个数字为0、3、6或9，则dp[i][j]也能被3整除，否则不能；如果dp[i-1][j]为1，则说明在前面的j个数字中有一个子序列能被3整除，此时如果第i个数字为1、4或7，则dp[i][j]也能被3整除，否则不能。

最终，我们只需要将dp数组中所有值等于1的元素的个数相加，并将结果对1e9+7取模即可。

以下是完整代码：

### 回答3：
题目描述

给定一个长度为50的数字串，求出其中有多少个子序列的和可以被3整除。输出对10^9+7取模的答案。

思路分析

我们可以先将给定的数字串转换成数字数组，将其看做是一个长度为n的数组a。我们令dp[i][0]为a[1]~a[i]中被3整除的子序列的个数,dp[i][1]为a[1]~a[i]中余1的子序列的个数，dp[i][2]为余2的子序列的个数。注意我们计算余数时可以直接用数值模3，余数就是该数值除以3的余数。

那么如果我们现在已经求出了dp[i-1][0],dp[i-1][1]和dp[i-1][2]，我们如何求dp[i][0],dp[i][1]和dp[i][2]呢？我们考虑当前数值a[i]对于这三种状态的影响：

如果a[i]可以被3整除，那么它可以加入到之前状态为0的所有子序列中，我们有dp[i][0] = dp[i-1][0] + 1，同时之前状态为1的子序列末尾加入该数后会变成状态为0的子序列，同样的，之前状态为2的子序列末尾加入该数也会变成状态为1的子序列，所以我们还需要加上dp[i-1][1]和dp[i-1][2]；

如果a[i]除以3余1，那么它可以加入到之前状态为2的所有子序列中，我们有dp[i][1] = dp[i-1][1] + 1，同时之前状态为0的子序列末尾加入该数后会变成状态为1的子序列，同样的，之前状态为1的子序列末尾加入该数也会变成状态为2的子序列，所以我们还需要加上dp[i-1][0]和dp[i-1][2]。

如果a[i]除以3余2，那么同理可以得到dp[i][2]的状态转移方程。

最终我们的答案即为dp[n][0]，因为被3整除的数字序列余数为0。同时，我们要注意答案需要对1e9+7取模。

时间复杂度为O(n)。

参考代码

这里给出Java代码实现：