文章中若有不严谨或错误的地方，欢迎在评论中指出QAQ

Description

题库链接

给出一个数 \(n\)，在其内任选一段连续的数删除，剩下的数拼接为一个新数，允许有前导零的出现，问所有拼接后可能出现的数的总和为多少，答案对 \(1e9+7\) 取模。

\(1 \le n < 10^{10^5}\)

Solution

设该数的长度为 \(m\)，则对于第 \(i\) 位上的数，我们考虑其左右两边的情况。

左边：

在左边删掉某段数，对于第 \(i\) 位上的数的系数没有任何影响，都为 \(a_i \times 10^{m-i}\)。

自己实验几组数据可以发现，其前面的情况共有 \(i \times (i-1) / 2\) 种。

所以对于左边第 \(i\) 位对总和的贡献为 \(i * (i - 1) / 2 \times 10 ^ {m - i} \times a_i\)

右边：

设 \(j\) 为第 \(i\) 位数右侧剩下的位数，那么 \(j\) 的范围就是 \(0 ~ m-i-1\)。

同理试验几组数据后可以看出，当剩 \(j\) 位时数量恰好为 \(j+1\) 个，此时第 \(i\) 位的贡献为 \(10^j \times a_i\)

所以对于右边第 \(i\) 位对总和的贡献为 \(\sum_ {j = 0 }^{m - i - 1} {(j + 1) \times 10 ^ j} \times a_i\)

然后对于每一位分别处理就可以得到答案，记得在过程中要取模，也不要忘记开 long long 。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7,p = 1e9+7;

typedef long long ll;

char s[N];

int main()
{
    scanf("%s",s+1);
    int m = strlen(s+1);
    
    ll tag = 1; // 记录10的次方
    ll tmp = 0; // 右侧的系数
    ll ans = 0; // 答案
    
    for (ll i = m ; i >= 1 ; i -- ) // i要开longlong，否则会超范围
    {
        int a = s[i] - ‘0‘;
        ans = (ans + i*(i - 1) / 2 % p * tag % p * a % p) % p;
        ans = (ans + tmp * a % p ) % p;
        tmp = (tmp +  (m-i+1) * tag % p) % p;
        tag = tag * 10 % p;
    }
    printf("%lld\n",ans);
    return 0;
}

Reference

Codeforces Tutorial

[Codeforces 1436C]Binary Search

原文：https://www.cnblogs.com/Crystar/p/14394552.html