https://codeforces.com/contest/1422/problem/C
大晚上算错数据范围的我，以为只有50位，直接暴力T5.然后发现是10000位。
贡献法优化，从低位往高位去枚举，也就是从后往前枚举。比如说枚举到第i位。
考虑第i位前进行连续区间的取。设可以取的整个区间范围为k.
可以发现，取1长的有k种，取2长的有k-2,取3长的有k-3...可以得出有k*(k+1)/2;
代入长度(i-1)可以得如果在第i位前面去取的话，这个数位的贡献是i*(i-1)*s[i]*pow[i];
考虑对第i位的后面的进行取。
举个例子。
8 4 3 2 1
对1来说，后面没有，那么贡献是0
对2来说，后面拿1，贡献是2
对3来说，后面拿1和2，贡献是3，后面拿1，贡献是30，后面拿2，贡献是30.
对4来说，后面拿123，贡献是4；后面拿23，21，贡献是40，40；后面拿3，2，1，贡献是400，400，400；
归纳起来就是
而后面的这个j*10^(j-1)可以累加更新得到。
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e5+100; typedef long long LL; const LL mod=1e9+7; LL sum[maxn]; char s[maxn]; int main(void) { //cin.tie(0);std::ios::sync_with_stdio(false); cin>>(s+1); LL len=strlen(s+1); LL ans=0; LL pw=1; LL sum=0; for(LL i=len;i>=1;i--) { LL num=i*(i-1)/2; ans=(ans%mod+(s[i]-'0')*pw%mod*num%mod)%mod; ans=(ans%mod+(s[i]-'0')%mod*sum%mod)%mod; sum=(sum%mod+(len-i+1)*pw%mod)%mod; pw=pw*10%mod; } cout<<ans<<endl; return 0; }
