题解：CF1422C Bargain

AC_OIKonjac · 2025-12-19 21:54:36 · 题解

Description

计算一个数字字符串中，所有可能的子串对应的数值之和，并对 10^9+7 取模。

Solution

对于字符串每一位数字 s_i，它能保留在结果中，当且仅当删除的连续子串不包含第 i 位。此时 s_i 的权重由其在结果中的位置决定（即 10^k，k 为其右侧保留的数字个数）。

定义 pre_i 为存储累加和 1 \times 10^0 + 2 \times 10^1 + ... + i \times 10^{i-1} \mod P，用于快速计算首位贡献。

当 s_i 不是结果的第一个字符时，说明其左侧至少保留了 1 个字符。

• 左侧保留的起始位置有 i-1 种选择（1 ~ i-1），删除的子串需在「左侧保留部分」和 d 之间（或左侧保留部分之前），最终左侧保留方式共 \frac{i \times (i-1)}{2} 种。
• 右侧保留的数字个数为 0 ~ n-i，对应的权重和为 10^0 + 10^1 + ... + 10^{n-i} = 10^{n-i+1} - 1。

贡献为 s_i \times \frac{i \times (i-1)}{2} \times 10^{n-i} \mod P（仅当 i \geq 2 时有此贡献）。

当 d 是结果的第一个字符时，其左侧所有字符都被删除（删除的子串结束于 i-1 位之前）。

右侧保留的数字个数为 0 ~ n-i，对应的权重和恰好是 pre_{n-i}。

贡献为 s_i \times pre_{n-i} \mod P。

第 i 位字符的总贡献为两种情况之和，将所有字符的总贡献累加即为最终答案。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 1, P = 1e9 + 7;

ll n, ans;
ll pre_s[N], Pow[N];
string s;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> s; n = s.size();
    s = " " + s;
    Pow[0] = 1;
    for (int i = 1; i <= n; i++) {
        Pow[i] = Pow[i - 1] * 10 % P;
        pre_s[i] = (pre_s[i - 1] + i * Pow[i - 1]) % P;
    }
    for (int i = 1; i <= n; i++) {
        if (i >= 2) {
            ll c1 = 1LL * i * (i - 1) / 2 % P;
            c1 = c1 * Pow[n - i] % P;
            c1 = c1 * (s[i] - '0') % P;
            ans = (ans + c1) % P;
        }
        ll c2 = 1LL * (s[i] - '0') * pre_s[n - i] % P;
        ans = (ans + c2) % P;
    }
    cout << ans;
    return 0;
}

Complexity Analysis

时空复杂度：\mathcal O(n)。