【题解】改造整数一

题意

给你一个长度为的整数，必须删除其中一段连续的数字，剩下的部分按顺序进行拼接形成一个新的数字，求所有可能的数字的和。

题解

考虑中每个数字的贡献，例如考虑的贡献，当删除的连续数字是在之后的即。那么若删除的长度为，可以有种不同的删法，那么的贡献为。若删除的长度为，同理有种不同的删法。所有贡献为。故在之后的删除可以表示为。
那么在考虑在之前删除数字，那么到末尾的长度一直不变，所有总的贡献是一样的有。
最后的答案就是统计每个数字的贡献然后加起来即可，可以用快速幂先预处理一下的次幂之和。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
char a[N];
long long f[N];
long long quickmod(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if (b%2==1)
            ans=(ans*a)%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{

    scanf("%s",a+1);
    int n=strlen(a+1);
    for(int i=1; i<=n; i++)
        f[i]=(f[i-1]+(i*quickmod(10,i-1)%mod))%mod;
    long long ans=0;
    for(int i=n; i>=1; i--)
    {
        ans=(ans+f[n-i]*(a[i]-'0')%mod)%mod;
        ans=(ans+(a[i]-'0')*quickmod(10,n-i)%mod*((1ll*i*(i-1)/2)%mod)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}