题解 | #被3整除的子序列# 余数DP的套路题

首先，定义状态：设 $d{p}_{i,j}dp\_\{i,j\}$ 表示数字串前 $ii$ 个数字的子序列中，模3余 $jj$ 的子序列个数。

然后，定义状态转移方程：设 $s_{i}s\_i$ 表示数字串中第 $ii$ 个数字，则状态转移方程为：

$d{p}_{i,j}=d{p}_{i-1,j}+d{p}_{i-1,(j-s_i\mathrm{m}\mathrm{o}\mathrm{d}3+3)\mathrm{m}\mathrm{o}\mathrm{d}3}dp\_\{i,j\}\; =\; dp\_\{i-1,j\}\; +\; dp\_\{i-1,(j-s\_i\; \backslash bmod\; 3\; +\; 3)\; \backslash bmod\; 3\}$

该方程的含义是：前 $ii$ 个数字的子序列中模3余 $jj$ 的子序列个数，等于前 $i-1i-1$ 个数字的子序列中模3余 $jj$ 的子序列个数（这些子序列中不包含第 $ii$ 个数字），加上前 $i-1i-1$ 个数字的子序列中模3余 $(j-s_i\mathrm{m}\mathrm{o}\mathrm{d}3+3)\mathrm{m}\mathrm{o}\mathrm{d}3(j-s\_i\; \backslash bmod\; 3\; +\; 3)\; \backslash bmod\; 3$ 的子序列个数（这些子序列中包含第 $ii$ 个数字）。 用通俗的语言来解释一下，有选与不选两种情况。如果不选，直接从前一个的相同余数转移过来。如果选，则计算出会从哪个余数转移过来。 额外地，我们需要考虑以当前数作为开头，方案数会+1。

根据上述状态和状态转移方程，我们可以写出如下代码，来求出数字串中模3余0的子序列个数：

void solve() {
  std::string s;
  std::cin >> s;
  const int MOD = 1e9 + 7;
  int n = s.size();
  std::vector dp(n + 1, std::vector(3, 0LL));
  for (int i = 1; i <= n; i++) {
    int x = s[i - 1] - '0';  // 第 i - 1 个数字
    
    // 状态转移方程
    dp[i][0] = (dp[i - 1][0] + dp[i - 1][(0 - x % 3 + 3) % 3]) % MOD;
    dp[i][1] = (dp[i - 1][1] + dp[i - 1][(1 - x % 3 + 3) % 3]) % MOD;
    dp[i][2] = (dp[i - 1][2] + dp[i - 1][(2 - x % 3 + 3) % 3]) % MOD;
    dp[i][x % 3]++;
  }

  // 输出结果
  std::cout << dp[n][0] << std::endl;
}  

其中很明显，状态转移方程的三行可以被一个for循环优化，这里不再赘述。