Introduction:

Link to the Problem

Forenote: This is my first blog so I'm open to any feedbacks.

Forenote 2: For anything here I am going to use 1-based indexing. Behave as if zero-based indexing does not exist :D

Let's extend the problem. You need to find the answer for the first $$$i$$$ digits for every $$$i$$$ such that $$$1 \leq i \leq N$$$. Constraint for $$$N$$$ is $$$1 \leq N \leq 2\times10^5$$$.

Note: My solution doesn't look alike the ones in editorial so make sure you don't skip any part of this blog (if you want to understand, of course). Even for the extended version, with my solution, some prefix sums and modular inverse is enough. I believe most people will be able to follow this editorial.

Enough words, let's get started :)

Building DP:

Let's associate a sequence $$$s$$$ with $$$S$$$ and let's map the value $$$s_i$$$ to the digit value of $$$S_i$$$.

Let $$$dp_i$$$ mean the answer for the first $$$i$$$ digits and let's try to calculate this.

For only the first digit, obviously $$$dp_1$$$ is equal to $$$s_1$$$. What is $$$dp_i$$$ for $$$2 \leq i \leq N$$$?

Below process is only for finding one $$$dp_i$$$, meaning that $$$i$$$ is a fixed value.

At this point, for simplicity, let's define a function $$$f$$$ and let $$$f(j, i) = 10^{i-j} s_j + 10^{i-j-1} s_{j+1} + ... + 10^2 s_{i-2} + 10^ 1 s_{i - 1} + 10^0 s_i$$$ for $$$1 \leq j \leq i \leq N$$$.

We are done with building our DP.

$$$dp_i = f(1, i) + \sum\limits_{j = 2}^{i} dp_{j - 1} + 2^{j - 2} f(j, i)$$$

This is an $$$O(N^4)$$$ solution if every aspect of it is implemented naively. Let's try applying some math to optimize it to something close to $$$O(N)$$$.

Math Time:

First we have to find some way to calculate $$$f(j, i)$$$ in $$$O(1)$$$ time. It turns out we can. Associate a sequence $$$d$$$ with $$$s$$$ such that $$$d_{N + 1} = 0$$$ and $$$d_i = d_{i+1} + 10^{N - i} s_i$$$ for $$$1 \leq i \leq N$$$. When we want a value of $$$f(j, i)$$$ we can simply get it with $$$\frac{d_j - d_{i+1}}{10^{N-i}}$$$. Reason is left as an exercise for the reader. Let's rewrite our DP without $$$f(j, i)$$$ this time.

$$$dp_i = 10^{i-N} (d_1 - d_{i + 1}) + \left[\sum\limits_{j = 1}^{i - 1}dp_{j}\right] + 10^{i-N} \left[\sum\limits_{j = 1}^{i - 1}2^{j - 1}d_{j+1}\right] - 10^{i-N} (2^{i - 1} - 1)d_{i+1}$$$

Let's associate variables $$$x$$$, $$$y$$$ with the second and third term respectively. Our $$$dp_i$$$ equation boils down to:

$$$dp_i = 10^{i-N}(d_1 - d_{i + 1}) + x + 10^{i-N}y - 10^{i-N}(2^{i-1}-1)d_{i+1}$$$

$$$dp_i = x + 10^{i-N}(d_1 - d_{i + 1} + y - (2^{i-1}-1)d_{i+1})$$$

$$$dp_i = x + 10^{-N}10^{i}(y + d_1 - 2^{i-1}d_{i+1})$$$

There it is, we can calculate some $$$dp_i$$$ in $$$O(1)$$$ if $$$x$$$ and $$$y$$$ is already computed before solving for $$$i$$$ and if the powers of $$$2$$$ and $$$10$$$ are precomputed. And when you're done with calculating $$$dp_i$$$ you can update $$$x$$$ and $$$y$$$ in $$$O(1)$$$ for next iteration. This makes up to $$$O(N)$$$ time. However, we have to the compute modular inverse of $$$10^N$$$ (which is equivalent to $$$10^{-N}$$$ above) before computing any $$$dp_i$$$ value. So you need a modular inverse algorithm. I like using Fermat's little theorem and it only involves binary exponentiation to the power of $$$M-2$$$ where $$$M$$$ is modulus. So the total time is $$$O(N + logM)$$$

Link to the accepted code is here but it only solves the original problem. But the only thing you have to modify is printing all the $$$dp_i$$$ values at last.

Thanks for bearing such a long post! Phew! I think it is time to get back to my mortal activities now (stolen complaint from this lovely comment). Sorry bicsi [orz] for stealing both your comment and your time spent on reading here to find the reason why you got pinged. You can read this btw, it really is basic math!