被3乘除的子序列

这个题目开始拿到手上不知道怎么设置状态转移，很多博客也没解释为什么那样转换是可以的。
首先我们要在数学上弄明白：mod 3，是非常特殊的，因为10%3=1,这有什么用呢。
如果目前1-i-1的某个子序列此时为x,取余3为k1，i位置数，取余3为k2,如果加上i位置的数的影响此时:
这个数就要变成10*x+a[i],对这个数取模mod：
(10*$x$+$a[i]$)%$mod$=((10%$mod$)$\ast$($x$*%$mod$)+$a[i]$%$mod$)%$mod$
$当mod=3,因为10mod3=1,所以上式等于（x+a[i])$%$mod$
所以当(x%mod+a[i]%mod)=0时就是答案的转移
dp[i][0]是前i个数子序列组成数字的所有能除3为0的集合的元素的个数， dp[i][1],dp[i][2]同理。
考虑dp[i+1][j]对应的集合中的元素（子序列），其构成可以分为如下三类：

只包括前i个数，即dp[i][j]对应的集合中所有元素都是满足的
只包括第i+1个数，这时要考虑第i+1个数mod 3的余数是多少，若为j则可为这个dp[i+1][j]对应的集合加把劲儿，否则不行。
包括第i+1个数，也包括前i+1个数。可以通过选出dp[i][k]对应集合的每一个元素，在后面添加第i+1个数，为看使得新构造的子序列mod 3 结果为j, k应该满足(k+A[i+1])%3应该为j.

上代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 60, mod = 1e9 + 7;
ll dp[N][3];
string s;int main() {cin >> s;dp[0][(s[0] - '0') % 3] = 1;int len = s.size();for (int i = 1; i < len; i++) {int m = (s[i] - '0') % 3;dp[i][m] = (dp[i][m] + 1) % mod; //单独kan i//在看 前i-1//最后看考虑 i的影响for (int j = 0; j < 3; j++) {dp[i][j] = (dp[i - 1][j] + dp[i - 1][(j - m + 3) % 3] + dp[i][j]) % mod;}}cout << dp[len - 1][0] % mod << "\n";return 0;
}