题目描述

难度分:$1300$

输入一个长度$\leq 3 \times 10^5$的数字字符串$s$。

输出$s$有多少个连续且非空的子串是$4$的倍数。

允许子串有前导零。

输入样例$1$

124

输出样例$1$

4

输入样例$2$

04

输出样例$2$

3

输入样例$3$

5810438174

输出样例$3$

9

算法

数学

如果是一位数，$0$、$4$、$8$能被$4$整除，否则只要后两位组成的二位数能被$4$整除即可。因此遍历$s$串，统计$0$、$4$、$8$的个数考虑一位数。然后继续遍历$s$串考虑二位数，如果$s[i-1:i]$能被$4$整除，就能为答案贡献$i-1$。

复杂度分析

时间复杂度

遍历两遍（也可以一遍）字符串$s$即可求出答案，时间复杂度为$O(n)$。

空间复杂度

除了输入的$s$串，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 300010;
char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '0' || s[i] == '4' || s[i] == '8') {
            ans++;
        }
    }
    for(int i = 2; i <= n; i++) {
        int num = (s[i - 1] - '0')*10 + (s[i] - '0');
        if(num % 4 == 0) {
            ans += i - 1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}