小苯的子串删除

[题目链接](https://www.nowcoder.com/practice/40de22ffa68740cca2193b3c9aa8fc7a)

思路

给定长度为 的数字串 ，可以最多进行一次操作：选择区间 删除这一段数位。问有多少种方案（包括不删除和全删除）使得剩余数字构成的数是 的倍数。

核心性质：整除 3 只看数位和

一个数是 的倍数，当且仅当其各数位之和是 的倍数。因此删除区间 后，剩余数字能被 整除等价于：

$$

即 。

特别地，全部删除时剩余为 ， 是 的倍数，所以 总是合法方案（也满足上式，因为 ）。不删除时需要 。

前缀和 + 计数

设 ，其中 。则：

$$

条件变为 ，即：

$$

从左到右扫描 ，用一个大小为 的计数数组 维护已扫描过的 中各余数的个数。对每个 ，计算需要的余数 ，将 累加到答案中，然后将 加入计数数组。

最后，若 ，还需额外 （不删除方案）。

复杂度

  • 时间复杂度：
  • 空间复杂度：

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    char s[200001];
    scanf("%s", s);
    int totalSum = 0;
    for(int i = 0; i < n; i++)
        totalSum = (totalSum + (s[i] - '0')) % 3;
    long long ans = 0;
    int cnt[3] = {1, 0, 0};
    int prefix = 0;
    for(int r = 1; r <= n; r++){
        prefix = (prefix + (s[r - 1] - '0')) % 3;
        int need = (prefix - totalSum + 3) % 3;
        ans += cnt[need];
        cnt[prefix]++;
    }
    if(totalSum == 0) ans++;
    printf("%lld\n", ans);
    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();
        int totalSum = 0;
        for (int i = 0; i < n; i++)
            totalSum = (totalSum + (s.charAt(i) - '0')) % 3;
        long ans = 0;
        int[] cnt = new int[3];
        cnt[0] = 1;
        int prefix = 0;
        for (int r = 1; r <= n; r++) {
            prefix = (prefix + (s.charAt(r - 1) - '0')) % 3;
            int need = (prefix - totalSum % 3 + 3) % 3;
            ans += cnt[need];
            cnt[prefix]++;
        }
        if (totalSum == 0) ans++;
        System.out.println(ans);
    }
}