Bargain

Given a number A. Remove some k length consecutive digits (substring) d(i),d(i+1),d(i+2)…..d(i+k) concatinate the rest of the digits. Find some of all such concatinated numbers after removing all possible non empty substrings less than n

Problem link here

Example

1021

All possible substring 1,10,102,021,21,1,02. 1021 is a substring but its length is the whole initial number so omit it.

The concatinated digits will then be 021,21,1,1,10,102,11. Now what we need is the sum 021+21+1+1+1+102+11.

Constraints

number of digits ≤ 10⁵

Solution

Let us first remove all the left substrings, meaning all substring starting at index 1 (substring[1 to i]) for i from 1 to n-1. Then the concatinated digits will be all the substring[i+1,n] whose values we need to sum up.

sum_of(value(substring[i+1,n])) call this subsdp(i)

In the above example we are calculating subsdp(i) as you can see

subsdp(10) = 3

subsdp(9) = 3+13 = 16

subsdp(8) = 16+13 = 29

Therefore subsdp(i) = subsdp(i+1)+substring_val(i to n)

We calculate this from right to left.

Similarly we remove left substrings and calculate subsdp(i) for right substrings.

Now we have handled all substrings that touch one of the edges that is index 1 or n.

Now all thats left out is adding up after removing substrings that lie in the middle.

notice that len(left) is only till n-2 because at n-1 you cannot remove any substring that does not touch either index 1 or n hence not being a mid substring.

as mentioned in the note above val(i) joins with the right substrings. We already have the value of the sumation of right substrings. Which is stored in subsdp. We need to add the value of subsdp(i+2) this is because we need to remove a mid substring hence that 1 length gap.

Now we need to add val(i) multiple times. lets says the right substring after the 1 length gap is 321. Then the right substring are 321,21,1

now val(i) will needs to be added at the different decimal places therefore val(i)*10³+321

val(i)*10²+21

val(i)*10+1

therfore summation = val(i)*(10+10²+….+10^(n-i-2)) + subsdp(i+2)

We cannot simplify like this because (a/b)%p != (a%p/b%p)%p

Now we can write mid_sum += val(i)*mul(i+2) + subsdp(i+2)

The final is therefore the mid_sum + left_sum + right_sum.

I have simplified some of unnecessary iterations, you can simplify the above equations to compute the answer in lesser iterations. But I don’t think we should spend more time than necessary on C problem 😛

Here is my messy implementation of the above.

note: mpow is modular exponentiation function

int main() {
    string s;cin>>s;
    vector<ll>a;
    for(auto c:s) a.pb(c-'0');
    int n = a.size();
    if(n<2) return !printf("0\n");
    
    ll subs[n+1], subsdp[n+1], val[n+1], mul[n+1];
    for(int i = n; i > 0; i--) {
        subs[i] = ((mpow(10*1LL,n-i)*a[i-1])%MOD +       
                    (i+1>n?0:subs[i+1]))%MOD;
        subsdp[i] = (subs[i] + (i+1>n?0:subsdp[i+1]))%MOD;
    }
    for(int i = 1; i <= n; i++) {
        val[i] = (a[i-1]+(i-1<1?0:val[i-1]*10))%MOD;
    }
    for(int i = n; i > 0; i --) 
        mul[i] = ((i+1>n?0:mul[i+1]) + mpow(10,n-i+1))%MOD;
    ll ans = 0;
    for(int i = 1; i < n; i++) {
        ans = (ans + ((val[i]*(i+2>n?1:mul[i+2]))%MOD + 
              (i+2>n?0:subsdp[i+2]))%MOD)%MOD;
        if(i+2 <= n)
        ans = (ans+val[i])%MOD;
    }
    ans = (ans + subsdp[2])%MOD;
    debug(ans);
}