本文共 1341 字，大约阅读时间需要 4 分钟。

本来是非常简单的一题…

一步想错步步想错…

很明显需要枚举每个数字来计算贡献

比如考虑第$i$位数字的贡献

$第一部分$

若删除$[i+1,n]$间的子串,删去长度为$j$的,还剩下$n-i-j$

贡献是$a[i]\ast \sum _{j=1}^{n-i}(n-i-j+1)\ast 10^{n-i-j}$

发现$n-i-j+1$的范围在区间$[1,n-i]$浮动

所以贡献就是$a[i]\ast \sum _{j=1}^{n-i}j\ast 10^{j-1}$

当考虑$i+1$位数字的贡献时$a[i+1]\ast \sum _{j=1}^{n-i-1}j\ast 10^{j-1}$

发现也就是少了一个$(n-i)\ast 10^{n-i-1}$

从前往后或从后往前都可以快速计算

$第二部分$

若删除$i$之前的子串,贡献是$a[i]\ast i\ast (i-1)/2$

#include 
   
    using namespace std;#define int long longconst int maxn = 2e5+10;const int mod = 1e9+7;char a[maxn];int one,ans;int quick(int x,int n){
   	int ans = 1;	for(;n;n>>=1,x=x*x%mod)		if( n&1 )	ans = ans*x%mod;	return ans;}signed main(){
   	cin >> (a+1);	int n = strlen( a+1 );	for(int i=n-1;i>=1;i--)	{
   		one = ( one+(n-i)*quick(10,n-i-1)%mod )%mod;		ans = ( ans+one*(a[i]-'0')%mod )%mod;		ans = ( ans+i*(i-1)/2%mod*(a[i]-'0')%mod*quick(10,n-i)%mod )%mod;	}	ans = ( ans+n*(n-1)/2%mod*(a[n]-'0')%mod )%mod;	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110243810 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！