被3乘除的子序列

这个题目开始拿到手上不知道怎么设置状态转移，很多博客也没解释为什么那样转换是可以的。

首先我们要在数学上弄明白：mod 3，是非常特殊的，因为10%3=1,这有什么用呢。

如果目前1-i-1的某个子序列此时为x,取余3为k1，i位置数，取余3为k2,如果加上i位置的数的影响此时:

这个数就要变成10*x+a[i],对这个数取模mod：

(10*x xx+a [ i ] a[i]a[i])%m o d modmod=((10%m o d modmod)∗ *∗(x xx*%m o d modmod)+a [ i ] a[i]a[i]%m o d modmod)%m o d modmod

当 m o d = 3 , 因 为 10 m o d 3 = 1 , 所 以 上 式 等 于 （ x + a [ i ] ) 当mod=3,因为10mod3=1,所以上式等于（x+a[i])当mod=3,因为10mod3=1,所以上式等于（x+a[i])%m o d modmod

所以当(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;
}