Codeforces Round #675 (Div. 2) C

这场真的够了...开局看d只有1500分就去开d了..40多分钟没开出来直接自闭放弃比赛，这会一看变成2300分了。。

欺骗感情不然这场完全可以手速上分的。

题意

给出一个长度为< 1e5 的正整数n
求解这个数删掉一个任意字串后留得的整数之和 求模1e9+7;

题解

对每位分别计算贡献。
对第i位，它可以进行贡献包括删它前面的字串和删它后面的字串，我们可以把他们分割成两个串分类考虑
对于删除的字串再当前位的前方，对于该位置的贡献影响，均为1ei * ai
对于删除的字串再当前位的后方，对于该位置的影响会随着删除的字串长度变化而变化，即当前贡献位
对于删除某长度的字符串的情况的种类数，很容易想到是
这样我们假设第i位前串长度为l，后串长度为r，那么第i位的总贡献即为

我们发现这么求解的时间复杂度是 这里n为这个数的值而非长度
这里第二个式子我们可以稍微化简一下，设 这个式子就是从
这个式子就变成了
这样两个值我们就都可以通过预处理得到。
###code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
using namespace std;

const ll maxn = 2e5 + 10;
const ll mod = 1e9 + 7;

ll inv[maxn];
ll fac[maxn];
ll F[maxn];

ll qpow(ll a,ll b)
{
   ll res = 1;
   while(b){
      if(b & 1) res = res * a % mod;
      a = a * a % mod;
      b >>= 1;
   }
   return res;
}

int main()
{
    string s;
    cin>>s;
    ll n = s.size();
    ll res = 0;
    for(ll i = 1;i < 2e5;++i){
        F[i] = (F[i-1] + i * qpow(10,i-1) % mod) % mod;
    }
    for(ll i = 0;i < n;++i){
        ll l = i,r = n-i-1;
        ll now = s[i] - '0';
        res = (res + now * (l * (l+1) / 2)%mod *qpow(10,r)) % mod;
        res = (res + now * F[r] % mod) % mod;
    }
    printf("%lld\n",res);

   return 0;
}