题解 | #被3整除的子序列#

如果一个数可以被$33$整除，那么这个数的每一位之和一定是$33$的倍数
证明:题解 | 3的倍数
定义：数组$dp[i][j]dp[i][j]$表示以$ii$为结尾组成的子序列，数位之和对$33$取余为$jj$的方案数
动态转换方程：
$num=(s[i]{-}^{\mathrm{\prime }}{0}^{\mathrm{\prime }})\mathrm{\%}3num=(s[i]-\text{'}0\text{'})\backslash \%3$ 表示本位取余$33$
$dp[i][(num+j)\mathrm{\%}3]+={\sum }_{k=0}^{k-1}dp[k][j]dp[i][(num+j)\backslash \%3]+=\backslash sum\_\{k=0\}^\{k-1\}\; dp[k][j]$
AC代码

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long dp[100][5];
int main(void)
{
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; i++)
	{
		int num = (s[i] - '0') % 3;
		dp[i][num]++;
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < i; k++)
			{
				dp[i][(num + j) % 3] = (dp[i][(num + j) % 3] + dp[k][j]) % mod;
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; i++)
		ans = (ans + dp[i][0]) % mod;
	cout << ans << endl;
}