原题:https://ac.nowcoder.com/acm/problem/21302

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

根据题目意思，我们直接考虑使用dp。
但是这个状态转移方程是真的不好想啊！

我们都知道可以被3整除的数，其各位数和能被3整除，那么我们只需要记录前i位，各位数和%3的情况，最后输出dp[length][0]即为答案。

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
const int m = 1e9 + 7;
int dp[55][3];
int main()
{
	string a;
	cin >> a;
	int l = a.length();
	int rest = (a[0]-'0') % 3;
	dp[0][rest] = 1;
	for (int i = 1; i < l; i++)
	{
		int rest = (a[i]-'0') % 3;
		dp[i][rest]++;
		for (int j = 0; j < 3; j++)
		{
			dp[i][j] += (dp[i - 1][j] + dp[i - 1][(j + 3 - rest) % 3]) % m;//若求得rest为1，那么当前这个rest，与前i-1位余数为1的情况，可以组成2，与前面余数为0的情况又可以组成1.
		}
	}
	cout << dp[l - 1][0] << endl;
}

dp[i][j] += (dp[i - 1][j] + dp[i - 1][(j + 3 - rest) % 3]) % m;
很容易理解的是，dp[i][j]得加上前i-1位余数为j的情况。
第二个就是要加上合成的情况。
比如说第i位的余数为2，那么我们加上前面i-1位余数为1情况，就可以合成余数为0的情况。
这个就是j+3-rest的含义。