题解

题面描述

给定一个仅由字符 $0,1,2,\ldots,9$ 组成的长度为 $n$ 的字符串 $t$。定义一个数字字符串的权值为其所有子串中同时满足以下两个条件的子串数量：

1. 子串所表示的整数为偶数，即末尾数字属于集合 $\{0,2,4,6,8\}$；
2. 子串不存在前导零（例如 “$02$” 或 “$020$” 均不合法），但单个字符 “$0$” 是合法的。

现在要求，对于给定的字符串 $t$，求其所有子串的权值之和。由于答案可能很大，输出结果需要对 $10^9+7$ 取模。

解题思路

我们可以从另外一个角度思考：
对字符串 $t$ 的每个有效子串（满足无前导零且末尾是偶数）都可以被看作其他更长子串的子串。具体来说，令 $u=t[i\ldots j]$ 为 $t$ 的一个子串，如果 $u$ 满足条件，则它在所有包含区间 $[i,j]$ 的子串中都出现，而这样的“父串”的数量为

其中 $i$ 表示 $u$ 左端点可以向前延伸的选择数（从 $1$ 到 $i$），而 $(n-j+1)$ 表示右端点可以向后延伸的选择数（从 $j$ 到 $n$）。

因此，只需要遍历 $t$ 的所有子串 $t[i\ldots j]$ 满足：

• 如果子串长度大于 $1$，则要求 $t[i]\neq 0$；
• 同时要求 $t[j] \in \{0,2,4,6,8\}$。

对每个满足条件的子串 $u$，其对最终答案的贡献为

为了高效求解，我们可以按右端点 $j$ 枚举：

• 当 $t[j]$ 为偶数时，对于固定的 $j$，所有满足条件的左端点 $i$ 可以拆为两部分：
  • $i=j$（长度 $1$ 始终合法，无论 $t[i]$ 是否为 $0$）；
  • $1 \le i \le j-1$ 且要求 $t[i]\neq 0$（保证没有前导零）。

如果我们事先维护前缀和数组
$S[j]$ = $\sum_{i=1}^{j}$ $\Bigl[ t[i] \neq '0' \Bigr] \times i$
那么对于位置 $j$（从 $1$ 开始计数），当 $t[j]$ 为偶数，其贡献即为

将所有贡献累加再取模即为答案。

代码分析

• 预处理：
  计算前缀和数组 $S$，其中 $S[j]$ 表示 $1 \le i \le j$ 且 $t[i]\neq '0'$ 的索引 $i$ 之和。
• 枚举右端点：
  对于每个位置 $j$（$1 \le j \le n$），若 $t[j] \in \{0,2,4,6,8\}$ 则累加贡献 $(n - j + 1) \times (S[j-1] + j)$，其中 $S[j-1]$ 表示前面合法（非 $0$）的位置之和。
• 取模：
  累加过程中注意对 $10^9+7$ 取模，保证数值不会过大。

代码实现

C++

#include <iostream>
#include <string>
using namespace std;
 
const long long MOD = 1000000007;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    string t;
    cin >> t;
    
    // 前缀和数组： S[i] 存储 1 到 i 中所有非 '0' 的位置之和
    long long prefixSum = 0;
    long long ans = 0;
    
    // 枚举右端点 j，从 1 开始计数，对应 t[j-1] 字符
    for (int j = 1; j <= n; j++){
        // 如果 t[j-1] 是非零，并且 j 小于当前 j（前缀贡献在 S[j-1] 中已维护）
        if(t[j-1] != '0'){
            prefixSum = (prefixSum + j) % MOD; 
        }
        // 判断 t[j-1] 是否为偶数字符
        char c = t[j-1];
        if(c == '0' || c == '2' || c == '4' || c == '6' || c == '8'){
            // 对于右端点 j 贡献： (n - j + 1) * (前缀合法贡献 + j)
            long long factor = (n - j + 1LL) % MOD;
            long long contribution = (prefixSum - ((t[j-1]!='0')? j:0) + j) % MOD;
            // 上述 contribution = S[j-1] + j，这里 prefixSum 中已经包含了 j
            // 若 t[j-1]!='0'，则 prefixSum = S[j-1] + j，所以需要减 j 后再加 j得到 S[j-1] + j
            // 如果 t[j-1]=='0'，prefixSum = S[j-1]，此时 contribution = S[j-1] + j
            if(contribution < 0) contribution += MOD;
            contribution = (contribution * factor) % MOD;
            ans = (ans + contribution) % MOD;
        }
    }
    
    cout << ans % MOD << "\n";
    return 0;
}

Python

# -*- coding: utf-8 -*-
MOD = 10**9 + 7

# 输入
n = int(input().strip())
t = input().strip()

# 前缀和变量：存储前面非 '0' 数字位置的索引和
prefix_sum = 0
ans = 0

# 枚举右端点 j，从 1 开始计数，对应 t[j-1]
for j in range(1, n+1):
    # 若当前字符不等于 '0'，则将位置 j 累加到前缀和中
    if t[j-1] != '0':
        prefix_sum = (prefix_sum + j) % MOD
    # 判断当前 t[j-1] 是否为偶数字符
    if t[j-1] in "02468":
        # 此时贡献为 (n - j + 1) * (S[j-1] + j)
        factor = (n - j + 1) % MOD
        # 注意：如果 t[j-1] != '0'，则 prefix_sum 中已经包含 j，
        # 所以 S[j-1] = prefix_sum - j；否则 S[j-1] = prefix_sum
        if t[j-1] != '0':
            contribution = ((prefix_sum - j) + j) % MOD  # = prefix_sum
        else:
            contribution = (prefix_sum + j) % MOD
        contribution = (contribution * factor) % MOD
        ans = (ans + contribution) % MOD

print(ans)

Java

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入字符串长度 n 和字符串 t
        int n = sc.nextInt();
        String t = sc.next();
        sc.close();
        
        long prefixSum = 0; // 保存前面非 '0' 数字位置的累加和
        long ans = 0;
        
        // 枚举右端点 j，注意下标从 1 开始计数，对应 t.charAt(j-1)
        for (int j = 1; j <= n; j++){
            char c = t.charAt(j - 1);
            // 若当前字符不为 '0'，则将位置 j 加入前缀和
            if(c != '0'){
                prefixSum = (prefixSum + j) % MOD;
            }
            // 判断当前字符是否为偶数字符
            if(c == '0' || c == '2' || c == '4' || c == '6' || c == '8'){
                long factor = (n - j + 1) % MOD; // (n - j + 1)
                long contribution;
                // 如果 c 不为 '0'，那么 prefixSum 包含了 j，本应使用 S[j-1] = prefixSum - j
                if(c != '0'){
                    contribution = ((prefixSum - j) + j) % MOD; // 等于 prefixSum
                } else {
                    contribution = (prefixSum + j) % MOD;
                }
                contribution = (contribution * factor) % MOD;
                ans = (ans + contribution) % MOD;
            }
        }
        System.out.println(ans);
    }
}

题目内容

小红定义，一个由$0,1,2,...,9$这十个数字构成的数字字符串的权值为，它的全部子串中，同时

满足下方这两个条件的数量:

$1.$字符串所表示的整数是偶数，即末尾数字属{$0,2,4,6,8$};

$2.$字符串不存在前导零(例如"$02$"或"$020$"均不合法)，但单个字符$0$ 是合法的。

小红现在想知道，对于给定的数字字符串$t$，它的全部子串的权值之和是多少。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

子串为从原字符串中，连续的选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

第一行:一个正整数$n(1 ≤n≤2×10^5)$代表字符串$t$的长度。

第二行:一个长度为$n$，仅由字符$0$到$9$组成的字符串$t$。

输出描述

一个整数，表示小红的数字字符串中所有子串的权值之和，结果对$10^9+7$取模。

样例1

输入

3
203

输出

9

说明

字符串“$203$"有六个子串:

• "$2$"，权值为$1$;
• "$0$"，权值为$1$;
• "$3$"，权值为$0$;
• "$20$"，权值为$3$;
• "$03$"，权值为$1$;
• "$203$"，权值为$3$; 综上，答案为 $9$

样例2

输入

3
202

输出

13