题目链接
一眼题 长度为1e5 QAQ 给我们一个数字字符串 操作若干次 每次移除它的子串，留下的数字重新拼接后 用ans累加起来 求最终的ans对1e9+7取模的结果 观察一下吧 ， 从低位开始 也就是从右到左 每位可以取到的次数为i*(i-1)/2 num 那么这样子分析，如果我们取的子串位于当前位的左边，那么对于现在这一位来说，贡献是没改变的 仍然是10^i *num 比如说111 从右往左 第一个1 产生的贡献为1乘num 因为无右边 所以右边贡献为0 第二个1 左边产生贡献为10 乘num 右边产生贡献为拿走i=3 则i=2处于最低位 产生1的贡献 第三个1 作为最高位 产生贡献100 * 0 右边都拿走了 产生1的贡献，右边任意拿走一个 产生2 * 10的贡献 总贡献为1 * 3+10 * 1+100 * 0+ 0+1+20+1 =35
好，很有精神，我们来看看1111的每位的右边贡献 321 21 1 0 好 更有精神 来看看11111 4321 321 21 1 0 为什么我一直拿全是1的字符串举例子呢 QAQ其实你对于1 的规律全部乘当前位的数不就是题目要的东西了 也没啥思维吧 就是个规律题
那么右边的贡献可以自己归纳下公式 我就不写了（逃
#include<bits/stdc++.h> #include<stdlib.h> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<time.h> #include <cstdio> #include <iostream> #include <vector> #define ll long long #define int long long #define inf 0x3f3f3f3f #define mods 1000000007 #define modd 998244353 #define PI acos(-1) #define fi first #define se second #define lowbit(x) (x&(-x)) #define mp make_pair #define pb push_back #define si size() #define E exp(1.0) #define fixed cout.setf(ios::fixed) #define fixeds(x) setprecision(x) #define IOS ios::sync_with_stdio(false);cin.tie(0) using namespace std; ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);} template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂% ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元 (分子*qp(分母,mod-2,mod))%mod; char s[1000006]; ll ve[3]; signed main(){ //ll n; //read(n); //n*n-1/2 //12 /* ll ok=12; ok=ok*(ok-1)/2; printf("%lld",n*ok%mods); */ scanf("%s",s+1); ll n=strlen(s+1); ll ans=0; ll vel=0; ll sum=0; ll poow=1; for(int i=n;i>=1;i--){ vel=(10*vel+sum)%mods; ll num=i*(i-1)/2; //printf("Q %lld %lld\n",(num%mods*poow)%mods*(s[i]-'0')%mods,vel); ans =(ans+(num%mods*poow+vel)%mods*(s[i]-'0'))%mods; sum =(sum+poow)%mods; poow =10*poow%mods; } printf("%lld\n",ans%mods); return 0; }