题解 | #小苯的子串删除#

题目链接

https://www.nowcoder.com/practice/40de22ffa68740cca2193b3c9aa8fc7a

思路分析

1. 问题转换与核心性质

题目要求我们计算有多少种删除连续子串的方案，使得剩余数字串代表的数是 3 的倍数。

一个众所周知的数学性质是：一个数是 3 的倍数，当且仅当它的各位数字之和是 3 的倍数。

利用这个性质，我们可以将问题从对数值的操作，转换为对各位数字之和的操作。

令 $S_{total}$ 为原数字串 $s$ 的各位数字之和。
令 $S_{deleted}$ 为被删除的子串的各位数字之和。
那么，剩余部分的数字之和为 $S_{remaining} = S_{total} - S_{deleted}$ 。

题目要求 $S_{remaining}$ 是 3 的倍数，即 $S_{remaining} \pmod 3 = 0$ 。根据模运算的性质，这等价于 $(S_{total} - S_{deleted}) \pmod 3 = 0$ ，也就是 $S_{total} \pmod 3 = S_{deleted} \pmod 3$ 。

因此，问题被转化为：

计算原串的数字和 $S_{total}$ 模 3 的余数，记为 $T = S_{total} \pmod 3$ 。
统计有多少种删除方案，使得被删除的子串的数字和 $S_{deleted}$ 模 3 的余数也等于 $T$ 。

删除方案包括：

不操作：如果原串数字和 $S_{total}$ 本身就是 3 的倍数（即 $T=0$ ），这是一种有效的方案。
删除子串：统计有多少个连续子串，其数字和模 3 等于 $T$ 。注意，删除整个字符串也是一种有效的删除方案，因为空串可以看作数字 0，是 3 的倍数。

2. 高效计数：前缀和

我们需要高效地统计所有满足条件的子串。如果暴力枚举所有 $O(N^2)$ 个子串并计算它们的和，总复杂度会达到 $O(N^3)$ ，无法通过。

这是一个经典的子数组/子串和问题，可以使用前缀和技巧进行优化。

令 $P_i$ 为字符串前 $i$ 个数字的和模 3 的余数，并规定 $P_0 = 0$ 。
那么，一个从索引 $l$ 到 $r$ (0-indexed) 的子串的数字和模 3，就等于 $(P_{r+1} - P_l + 3) \pmod 3$ 。

我们需要寻找的，是满足 $(P_{r+1} - P_l + 3) \pmod 3 = T$ 的 (l, r) 对的数量。这个等式可以变形为： $P_l \equiv (P_{r+1} - T) \pmod 3$ 。

我们可以通过一次遍历来解决这个问题：当我们从左到右遍历字符串，计算出每个前缀和 $P_j$ (其中 $j = r+1$ ) 时，我们只需要查询在它之前，有多少个前缀和 $P_l$ 满足 $P_l \equiv (P_j - T) \pmod 3$ 即可。

为了实现快速查询，我们可以用一个大小为 3 的数组 count，分别记录值为 0, 1, 2 的前缀和已经出现过的次数。

3. 算法步骤

计算整个字符串的数字之和模 3 的余数 $T$ 。
初始化答案 ans = 0。如果 $T=0$ ，则“不操作”是一种有效方案，ans = 1。
初始化一个频率数组 count = [0, 0, 0]。因为空前缀（ $P_0$ ）的和为 0，所以 count[0] = 1。
初始化当前前缀和 current_sum_mod_3 = 0。
从左到右遍历字符串中的每个数字 d： a. 更新当前前缀和：current_sum_mod_3 = (current_sum_mod_3 + d) % 3。 b. 计算我们需要的“目标”旧前缀和：target_prefix_mod = (current_sum_mod_3 - T + 3) % 3。 c. 在 count 数组中查找 target_prefix_mod 出现的次数，将其累加到 ans 中。这代表以当前位置为结尾的、所有满足条件的子串数量。 d. 将当前前缀和 current_sum_mod_3 的出现次数加一：count[current_sum_mod_3]++。
遍历结束后，ans 就是最终的方案数。注意 ans 可能会很大，需要使用 64 位整型存储。

代码

cpp
java
python

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    long long total_sum_mod_3 = 0;
    for (char c : s) {
        total_sum_mod_3 = (total_sum_mod_3 + (c - '0')) % 3;
    }

    long long ans = 0;
    if (total_sum_mod_3 == 0) {
        ans = 1; // 不操作
    }

    vector<long long> count(3, 0);
    count[0] = 1; // 空前缀的和为0
    int current_sum_mod_3 = 0;

    for (char c : s) {
        current_sum_mod_3 = (current_sum_mod_3 + (c - '0')) % 3;
        int target_prefix_mod = (current_sum_mod_3 - total_sum_mod_3 + 3) % 3;
        ans += count[target_prefix_mod];
        count[current_sum_mod_3]++;
    }

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        long totalSumMod3 = 0;
        for (char c : s.toCharArray()) {
            totalSumMod3 = (totalSumMod3 + (c - '0')) % 3;
        }

        long ans = 0;
        if (totalSumMod3 == 0) {
            ans = 1; // 不操作
        }

        long[] count = new long[3];
        count[0] = 1; // 空前缀的和为0
        int currentSumMod3 = 0;

        for (char c : s.toCharArray()) {
            currentSumMod3 = (currentSumMod3 + (c - '0')) % 3;
            int targetPrefixMod = (int)((currentSumMod3 - totalSumMod3 + 3) % 3);
            ans += count[targetPrefixMod];
            count[currentSumMod3]++;
        }

        System.out.println(ans);
    }
}

import sys

def solve():
    try:
        n = int(sys.stdin.readline())
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return
        
    digits = [int(c) for c in s]
    
    total_sum_mod_3 = sum(digits) % 3
    
    ans = 0
    if total_sum_mod_3 == 0:
        ans = 1 # 不操作
        
    count = [0, 0, 0]
    count[0] = 1 # 空前缀的和为0
    current_sum_mod_3 = 0
    
    for d in digits:
        current_sum_mod_3 = (current_sum_mod_3 + d) % 3
        target_prefix_mod = (current_sum_mod_3 - total_sum_mod_3 + 3) % 3
        ans += count[target_prefix_mod]
        count[current_sum_mod_3] += 1
        
    print(ans)

solve()

算法及复杂度

算法：前缀和 + 哈希计数
时间复杂度： $O(N)$ ，其中 $N$ 是数字串的长度。我们只需要对字符串进行常数次遍历。
空间复杂度： $O(N)$ ，用于存储输入的字符串。如果边读边处理，额外空间复杂度可以降至 $O(1)$ 。