Codeforces Round #675 (Div. 2)C. Bargain

前言:硬石を切ったので、メモしておきます.テーマゲート
C.Bargainテーマを分析する前に、私たちはまずこのような思想を導入します:分位して貢献を求めます.1つの数について、例えば、5037489は、7番目が9であり、全体の数に対する寄与は9*(10^0)=9であり、6番目が8であり、全体の数に対する寄与は8*(10^1)=80である.  の下で私たちは次第に難易度を増加して、5037489に対して、私たちはその中の2位から5位まで削除して、つまり374で、374の右の数の貢献は変わらないことを発見することができて、左の数の貢献は10^3倍縮小しました.このようにして、ある桁数に対して、その左側の一部を削除して、その貢献は変わらないという法則を得ました.右側のk個数を削除し,寄与を10^k縮小する.  タイトルでは,すべての削除セグメントを求める場合に,残りの数の組合せを列挙するだけで,各iを列挙し,その左の1~i-1個数を削除する寄与を求め,右の1~n-iを削除する寄与を加える.最后の问题:どのようにO(1)を求めて右の贡献を削除しますか?私たちは右から左へ考えます.5037489,8に対して右側0ビットを保持する1つの方法.  は4に対して、右側の0ビットを保持することができ、1つの方法である.1ビット保持、2つの方法.7に対して、右側の0ビットを保持することができ、1つの方法;1ビット保持、2つの方法;2ビット保持、3つの方法.  は,異なる同位体での数字が右の同じ数の桁数を保持する方法数が同じであることが分かった.  では,i位のビット数寄与をC[i]とすると,C[i]=C[i-1]+(n-i)*(10^(n-i-1))となる.第i位の総貢献はa[i]*c[i].  **左のを削除すればいいので、簡単には言いません.**
  code:

#include 
#define mod 1000000007
using namespace std;
 
long long n,ans,C = 0,mi10[101010],pre[101010];
char a[101010];
 
int main()
{
     
    ios::sync_with_stdio(false);
    cin >> a+1 ;
    n = strlen(a+1);
    mi10[0] = 1;
    for(int i = 1 ; i <= n ; ++i){
     
        mi10[i] = (mi10[i-1] * 10)%mod;
        pre[i] = (pre[i-1] + i)%mod;
    }
    for(int i = n-1 ; i >= 1 ; --i){
     
        C = (C + mi10[n-i-1]*(n-i)%mod)%mod;
        ans = (ans + ((a[i]-'0')*C)%mod )%mod;
    }
    for(int i = 2 ; i <= n ; ++i){
     
        ans = (ans + pre[i-1]*(a[i]-'0')%mod*mi10[n-i]%mod)%mod;
    }
    cout << ans << endl ;
    return 0;
}