定义状态：dp[i][j]表示前i个数字中，数字之和除以3余数为j的子序列的个数。 状态转移方程： 当当前数字num除以3的余数为0时： dp[i][0] = (dp[i-1][0] * 2 + 1) % mod，因为可以选择不选当前数字，此时有dp[i - 1][0]种情况；也可以选择选当前数字，此时有dp[i - 1][0]种情况，再加上当前数字本身构成的一种情况。 dp[i][1] = (dp[i - 1][1] * 2) % mod，因为选择不选当前数字，有dp[i - 1][1]种情况；选择选当前数字，此时和仍不能被3整除。 dp[i][2] = (dp[i - 1][2] * 2) % mod，同理。 当当前数字num除以3的余数为1时： dp[i][0] = (dp[i - 1][2] + dp[i - 1][0]) % mod，因为前i - 1个数字之和除以3余数为2或0时，加上当前数字可以使得和能被3整除。 dp[i][1] = (dp[i - 1][0] + 1 + dp[i - 1][1]) % mod，因为前i - 1个数字之和除以3余数为0时，加上当前数字可以使得和除以3余数为1；当前数字本身也构成一种余数为1的情况；前i - 1个数字之和除以3余数为1时，加上当前数字仍余数为1。 dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod，同理。 当当前数字num除以3的余数为2时： dp[i][0] = (dp[i - 1][1] + dp[i - 1][0]) % mod，同理。 dp[i][1] = (dp[i - 1][2] + dp[i - 1][1]) % mod，同理。 dp[i][2] = (dp[i - 1][0] + 1 + dp[i - 1][2]) % mod，同理。 最终答案为dp[n][0]，其中n为字符串的长度。 在实现时，可以使用一个二维数组来存储状态，然后从左到右依次计算每个数字的状态转移。

定义二维数组 dp[i][j]，其中 i 表示考虑到字符串的前 i 个数字，j 的取值为 0、1、2，分别代表数字之和除以 3 的余数为 0、1、2 的情况。 初始时，dp[0][0] = 1，因为当没有数字时（即第 0 个位置），数字之和除以 3 余数为 0 的子序列个数为 1（即空序列）。其他 dp[0][1] 和 dp[0][2] 都为 0。 计算状态转移 对于字符串中的每个数字（从第 1 个数字开始），我们先计算其除以 3 的余数 num % 3，假设结果为 r （r 的值为 0、1 或 2）。 当 r = 0 时： dp[i][0] = (dp[i - 1][0] * 2 + 1) % mod ：对于前 i - 1 个数字能构成余数为 0 的子序列，有两种选择，要么不包含当前数字，此时有 dp[i - 1][0] 种情况；要么包含当前数字，此时也有 dp[i - 1][0] 种情况，再加上当前数字单独构成的一种情况。 dp[i][1] = (dp[i - 1][1] * 2) % mod ：对于前 i - 1 个数字能构成余数为 1 的子序列，同样有两种选择，不包含当前数字有 dp[i - 1][1] 种情况，包含当前数字则和仍不能被 3 整除。 dp[i][2] = (dp[i - 1][2] * 2) % mod ：对于余数为 2 的情况，逻辑与上述类似。 当 r = 1 时： dp[i][0] = (dp[i - 1][2] + dp[i - 1][0]) % mod ：如果前 i - 1 个数字之和除以 3 余数为 2 或 0，加上当前数字就能使和能被 3 整除。 dp[i][1] = (dp[i - 1][0] + 1 + dp[i - 1][1]) % mod ：如果前 i - 1 个数字之和除以 3 余数为 0，加上当前数字能使和除以 3 余数为 1；当前数字本身构成余数为 1 的一种情况；如果前 i - 1 个数字之和除以 3 余数为 1，加上当前数字和的余数仍为 1。 dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod ：同理，对于余数为 2 的情况进行状态转移。 当 r = 2 时： 状态转移的逻辑与 r = 1 时类似，只是余数的组合不同。 最终答案 经过上述步骤计算完所有数字后，最终答案为 dp[n][0]，其中 n 是字符串的长度。这表示考虑整个字符串时，数字之和除以 3 余数为 0 的子序列的个数。 例如，假设有字符串 "120"： 对于第一个数字 1（余数为 1）： dp[1][0] = dp[0][2] + dp[0][0] = 0 + 1 = 1 dp[1][1] = dp[0][0] + 1 + dp[0][1] = 1 + 1 + 0 = 2 dp[1][2] = dp[0][1] + dp[0][2] = 0 + 0 = 0 对于第二个数字 2（余数为 2）： dp[2][0] = dp[1][1] + dp[1][0] = 1 + 1 = 2 dp[2][1] = dp[1][2] + dp[1][1] = 0 + 2 = 2 dp[2][2] = dp[1][0] + 1 + dp[1][2] = 1 + 1 + 0 = 2 对于第三个数字 0（余数为 0）： dp[3][0] = (dp[2][0] * 2 + 1) % mod = (2 * 2 + 1) % mod = 5 % mod dp[3][1] = (dp[2][1] * 2) % mod = (2 * 2) % mod = 4 % mod dp[3][2] = (dp[2][2] * 2) % mod = (2 * 2) % mod = 4 % mod 最终答案为 dp[3][0] ，即 5（取模后的值）。