如果一個數(shù)可以被$33$整除，那么這個數(shù)的每一位之和一定是$33$的倍數(shù)
證明:題解 | 3的倍數(shù)
定義：數(shù)組$dp[i][j]dp[i][j]$表示以$ii$為結(jié)尾組成的子序列，數(shù)位之和對$33$取余為$jj$的方案數(shù)
動態(tài)轉(zhuǎn)換方程：
$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;
}