number - 题解

标签与难度

标签: 动态规划, 数学, 字符串, 前缀和, 数论, DP 难度: 1700

题目大意喵~

你好呀，未来的算法大师！今天我们遇到了一道有趣的数字题，喵~

题目是这样的：给定一个只包含数字字符的字符串 S，我们需要找出其中有多少个子串，当被看作一个十进制整数时，是 300 的倍数。

这里有几个需要注意的小细节哦：

子串允许有前导零。比如在 "0300" 中，"0300" 本身就是一个合法的子串，代表整数 300。
子串 "0" 或者 "00" 都代表整数 0，而 0 是任何非零整数的倍数，所以 0 也是 300 的倍数。
同一个数值的子串，如果出现在不同位置，要分别计数。比如 "300300" 中的两个 "300" 就要算作两次。

简单来说，就是统计所有能被 300 整除的子串的出现次数，呐。

解题思路分析

这道题看起来和数字有关，那我们就从数字的性质入手吧，喵~

一个数要想成为 300 的倍数，需要满足什么条件呢？ $300 = 3 \times 100$ 。因为 3 和 100 是互质的，所以一个数要被 300 整除，当且仅当它同时被 3 和 100 整除。

我们来分别看看这两个条件：

被 100 整除：一个整数被 100 整除，要么它就是 0，要么它的十进制表示末尾是 "00"。
- 对于子串来说，如果它代表的数是 0，那么这个子串本身必须是由一个或多个 '0' 组成的，比如 "0", "00", "000" 等。
- 如果它代表的数非 0，那么这个子串必须以 "00" 结尾。
被 3 整除：这是一个经典的数论知识点！一个数能被 3 整除，当且仅当它的各位数字之和能被 3 整除。例如，369 的数字和是 $3+6+9=18$ ，18能被3整除，所以369也能被3整除。

把这两个条件结合起来，一个子串 S[i..j] 要是 300 的倍数，就必须满足： [ (子串代表的数是 0) 或者 (子串以 "00" 结尾) ] 并且 [ 子串的各位数字之和能被 3 整除 ]

这个逻辑有点绕，我们换个角度来分类计数，让问题变得更清晰！我们可以把所有满足条件的子串分成两类，这两类之间没有交集，这样加起来就是总答案啦。

第一类：长度为 1 的合法子串 只有一个长度为 1 的子串能被 300 整除，那就是 "0" 本身。所以，我们只需要数一数原字符串里有多少个 '0' 字符就行啦。
第二类：长度大于等于 2 的合法子串 一个长度大于等于 2 的子串要被 300 整除，它必须满足：
1. 子串以 "00" 结尾。
2. 子串的各位数字之和能被 3 整除。

这样分类是不是瞬间清晰了，喵？我们分别计算这两类的数量，然后加起来！

如何高效地计算第二类的数量呢？

我们可以遍历整个字符串，当我们找到一个以 "00" 结尾的位置时，再回头去找所有合法的起点。假设我们遍历到索引 i，发现 S[i-1] == '0' 并且 S[i] == '0'。这时，我们就找到了一个合法的结尾 S[...i]。接下来，我们需要计算有多少个起始位置 j <= i-1，使得子串 S[j..i] 的数字和是 3 的倍数。

暴力去枚举 j 再求和肯定会超时，所以我们需要一个更快的办法。这正是前缀和与动态规划大显身手的时候！

我们可以维护一个动态规划状态。让我们定义 dp[k] 为：以当前位置 i-1 结尾的子串中，有多少个子串的数字和模 3 的余数是 k。

当我们处理到位置 i 时，我们可以利用 dp 数组（即 i-1 的状态）来计算出以 i 结尾的子串信息。令 val = S[i] - '0'。一个以 i 结尾的子串，要么是 S[i] 单独一个字符，要么是在一个以 i-1 结尾的子串后面追加 S[i]。

对于以 i-1 结尾的、数字和模 3 余 k 的子串，在后面添上 S[i] 后，新的子串数字和模 3 的余数就变成了 (k + val) % 3。
对于 S[i] 本身，它形成了一个新的子串，数字和模 3 余 val % 3。

所以，我们可以从 i-1 的状态 dp_prev 推导出 i 的状态 dp_curr： dp_curr[(k + val % 3) % 3] = dp_prev[k] for k=0,1,2dp_curr[val % 3]++ (别忘了算上 S[i] 自己！)

有了这个DP思想，我们的算法流程就出来啦：

初始化 ans = 0。
初始化一个大小为 3 的计数数组 counts = {0, 0, 0}，代表以当前位置的前一个位置结尾的子串，其数字和模 3 分别为 0, 1, 2 的数量。
遍历字符串 S，从左到右，索引为 i： a. 如果 S[i] == '0'，那么 "0" 是一个合法的子串，ans++。 b. 计算 val = S[i] - '0'。 c. 根据上面的递推关系，计算出以 i 结尾的子串的计数 new_counts。 * new_counts[0] = counts[(0 - val % 3 + 3) % 3] * new_counts[1] = counts[(1 - val % 3 + 3) % 3] * new_counts[2] = counts[(2 - val % 3 + 3) % 3] * new_counts[val % 3]++ d. 如果 i > 0 且 S[i-1] == '0' 且 S[i] == '0'，说明我们找到了一个 "00" 结尾。此时，以 i 结尾的子串中，数字和能被 3 整除的有 new_counts[0] 个。这些子串都以 "00" 结尾（因为它们的长度都大于等于2），所以它们都满足第二类的条件！我们就把它们的数量加入 ans。 * ans += new_counts[0] e. 更新 counts = new_counts，进入下一次迭代。

咦？这个逻辑好像有点小问题。在 new_counts[0] 中，有一个子串是 S[i] 自己，也就是 "0"。这个 "0" 长度为 1，我们已经在第一类里统计过了！为了避免重复计算，我们应该加上 new_counts[0] - 1。

所以最终的算法是：

初始化 ans = 0。
初始化 counts = {0, 0, 0}。
遍历字符串 S (索引 i 从 0 到 n-1): a. val = S[i] - '0'。 b. 计算 new_counts。 c. 如果 S[i] == '0'，ans++。 d. 如果 i > 0 且 S[i-1] == '0' 且 S[i] == '0'，ans += new_counts[0] - 1。 e. counts = new_counts。

这样，我们就在一次遍历中，优雅地解决了问题，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份代码~ 注释很详细的哦！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>

// 使用 long long 来防止答案溢出，喵~
using ll = long long;

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string s;
    std::cin >> s;

    ll total_ans = 0;
    
    // dp_counts[k] 表示以 i-1 位置结尾的子串中，
    // 数字和模3余k的数量。
    // 初始时，在字符串开始前，没有任何子串，所以都为0。
    std::vector<ll> dp_counts(3, 0);

    for (int i = 0; i < s.length(); ++i) {
        int current_digit = s[i] - '0';
        int current_digit_mod_3 = current_digit % 3;

        // 准备计算以当前位置 i 结尾的子串信息
        std::vector<ll> new_dp_counts(3, 0);

        // 状态转移：
        // 一个以 i 结尾的子串，是在一个以 i-1 结尾的子串后追加 s[i] 得到的。
        // 如果之前子串和模3余k，现在就余 (k + current_digit_mod_3) % 3
        for (int k = 0; k < 3; ++k) {
            new_dp_counts[(k + current_digit_mod_3) % 3] += dp_counts[k];
        }
        
        // 别忘了 s[i] 本身也构成一个新子串
        new_dp_counts[current_digit_mod_3]++;

        // --- 开始计算并累加答案 ---

        // 情况一：子串就是 "0"。
        // 任何单个 '0' 字符构成的子串都代表数字0，0是300的倍数。
        if (current_digit == 0) {
            total_ans++;
        }

        // 情况二：子串长度 >= 2，以 "00" 结尾，且数字和是3的倍数。
        if (i > 0 && s[i-1] == '0' && s[i] == '0') {
            // new_dp_counts[0] 是以 i 结尾的、数字和能被3整除的子串总数。
            // 这些子串因为都以 '...00' 结尾，所以都满足被100整除。
            // 因此，它们都是300的倍数。
            // 但是，new_dp_counts[0] 包含了一个长度为1的子串 "0" (即s[i]本身)，
            // 这个我们已经在情况一中数过了，所以要减去1，避免重复计数。
            total_ans += new_dp_counts[0] - 1;
        }

        // 更新dp状态，为下一次迭代做准备
        dp_counts = new_dp_counts;
    }

    std::cout << total_ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只对长度为 $N$ 的字符串进行了一次完整的遍历。在循环的每一步中，我们做的都是常数时间的操作（更新一个大小为3的数组），所以总的时间复杂度是线性的，喵~
空间复杂度: $O(1)$ 我们只使用了几个变量和一个固定大小为 3 的 dp_counts 数组来存储DP状态，占用的空间是常数级别的，和输入字符串的长度无关。

知识点总结

这道题是数论和动态规划的完美结合，真是太有趣啦！

数论知识: 解决问题的关键是拆解 "被300整除" 这个条件，把它变成 "被3整除" 和 "被100整除" 两个子问题。
动态规划 (DP): 我们用DP来高效地统计满足特定条件的子串数量。这里的DP状态定义非常巧妙，dp[k] 表示以某个位置结尾的、数字和模3余k的子串个数，使得我们可以在 $O(1)$ 的时间内完成状态转移。
分类讨论与不重不漏: 将所有合法子串分为 "长度为1" 和 "长度大于等于2" 两类，确保了我们计算时既没有遗漏任何情况，也没有重复计算。那个 -1 的小细节就是为了保证不重复，是解题的画龙点睛之笔呢！

希望这篇题解能帮到你！继续加油，你一定可以成为更厉害的算法大师的，喵~！

number - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​