要解决这个问题，即给定一个长度不超过50的数字字符串，计算所有非空子序列（子序列定义为从原序列中删除零个或多个字符后形成的序列，顺序保持不变）中，其构成的数字能被3整除的个数，答案需对 (10^9 + 7) 取模。

解题思路

一个数字可以被3整除当且仅当其各位数字之和能被3整除。因此，问题转化为寻找所有非空子序列，使得子序列的数字之和模3等于0。

使用动态规划（DP）来解决：

  • 状态定义：dp[j] 表示考虑当前字符时，子序列数字和模3余 j 的个数（包括空序列），其中 j 取值为0、1、2。
  • 初始化：初始时（空序列），dp[0] = 1（空序列和为0），dp[1] = 0，dp[2] = 0。
  • 状态转移：对于字符串中的每个字符，其数字值为 d，计算 d_mod = d % 3（值为0、1或2）。更新DP状态：
    • 对于每个余数 j（0、1、2），计算新余数 k = (j - d_mod + 3) % 3（确保 k 非负）。
    • 更新公式：new_dp[j] = (dp[j] + dp[k]) % mod，其中 dp[j] 表示不选当前字符，dp[k] 表示选当前字符（因为选当前字符时，新余数为 (k + d_mod) % 3 = j）。
  • 更新DP：处理完每个字符后，用 new_dp 更新 dp。
  • 结果：最终 dp[0] 包含空序列，因此非空子序列中数字和模3余0的个数为 (dp[0] - 1) % mod。

代码实现

#include <iostream>
#include <string>
using namespace std;

const int mod = 1000000007;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    // dp[j] 表示子序列和模3余j的个数（包括空序列）
    long long dp[3] = {1, 0, 0}; // 初始化：空序列和为0

    for (int i = 0; i < n; i++) {
        int d = s[i] - '0'; // 字符转数字
        int d_mod = d % 3; // 取模3，值为0、1或2
        long long new_dp[3] = {0, 0, 0}; // 临时数组存储新状态

        // 更新每个余数状态
        for (int j = 0; j < 3; j++) {
            int k = (j - d_mod + 3) % 3; // 计算旧余数k，确保非负
            new_dp[j] = (dp[j] + dp[k]) % mod;
        }

        // 复制回dp数组
        for (int j = 0; j < 3; j++) {
            dp[j] = new_dp[j];
        }
    }

    // 结果：非空子序列个数（排除空序列）
    long long ans = (dp[0] - 1) % mod;
    if (ans < 0) ans += mod; // 确保非负
    cout << ans << endl;

    return 0;
}

代码解释

  1. 输入处理：读取字符串 s。
  2. 初始化DP数组：dp[0] = 1（空序列），dp[1] = 0，dp[2] = 0。
  3. 遍历字符串：对每个字符：
    • 计算其数字值 d 和模3值 d_mod。
    • 初始化 new_dp 为 {0, 0, 0}。
    • 对于每个余数 j（0、1、2）：
      • 计算旧余数 k = (j - d_mod + 3) % 3（加3确保非负）。
      • 更新 new_dp[j] = (dp[j] + dp[k]) % mod（不选和选当前字符的贡献）。
    • 将 new_dp 复制到 dp。
  4. 输出结果：dp[0] - 1 即为非空子序列中数字和模3余0的个数，取模并确保非负后输出。

此方法时间复杂度为 (O(n))（(n) 为字符串长度），空间复杂度为 (O(1))，高效适用于长度不超过50的字符串。