POWERSOF10 - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kulyash
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093






You’re given a large number N. Perform the following operation K times and print the length of the resulting number:

  • Write N as the minimal sum of powers of 10 (for example, 123 = 100 + 10 + 10 + 1 + 1 + 1). Then, concatenate these powers in order to form the new value of N


If K = 0 the answer is just the length of N.

Otherwise, let’s perform the operation on N once and then decrease K by 1.
Notice that the resulting number now contains only the digits 0 and 1; in fact, any further number we create will also consist of only 0's and 1's.
Also notice that the number we created has at most 9 \log_{10}N ones, since this is the maximum number of powers of 10 we can extract.

Let’s see what happens when we perform the operation on such a number.

Suppose N = 10^{k_1-1} + 10^{k_2-1} + \ldots + 10^{k_r-1} where k_1 \gt k_2 \gt \ldots \gt k_r \geq 1.
Note that the length of N is currently k_1, and in particular k_i is the length of 10^{k_i - 1}.

Now perform the operation once. We’ll again get exactly r powers of 10, let their lengths be l_1 \gt l_2 \gt \ldots \gt l_r \geq 1.
Working out the details, you can see that:

  • l_r = k_r
  • l_{r-1} = k_r + k_{r-1}
  • l_{r-2} = k_r + k_{r-1} + k_{r-2}

More generally, l_i = \sum_{j=i}^r k_j.

Notice that we’re just taking the suffix sum of the array [k_1, k_2, \ldots, k_r] to obtain l.
Also note that the length of the resulting number is l_1.

This tells us a way to get to the final answer: compute the array [k_1, \ldots, k_r] from the N we have, then take its suffix sum K times (recall that we decreased K by 1 earlier), and finally print the first element of this suffix sum.

However, K is quite large so directly computing the suffix sum K times is not possible.

Subtask 1

One way of quickly computing suffix sums multiple times is to use matrix exponentiation.

This is an application of a more general technique to quickly compute linear recurrences, a quick tutorial can be found here.

In the case of suffix sums of an array A, we want to iteratively compute suf_i = A_i + A_{i+1} + \ldots + A_r.
The result is linear in terms of the values of A, so it’s possible to find a matrix that encapsulates this information; in particular the r\times r matrix M with M_{i, j} = 1 if and only if i \leq j is what we want.

Note that multiplying M with [A_1, A_2, \ldots, A_r]^T gives us exactly [suf_1, suf_2, \ldots, suf_r]^T. Then we can multiply M with the result, and so on K times.
So, the answer we want is to compute the product of M^K with [A_1, A_2, \ldots, A_r]^T and then look at its first element.

Computing M^K can be done in \mathcal{O}(r^3 \log K) time using matrix exponentiation: use binary exponentiation as you would to compute a^b, except the multiplication is now matrix multiplication.

In the first subtask, N \leq 1000 which gives us r \leq 9\cdot 4 = 40, so this works in about 40^3 \log K operations per test, which is fast enough.

Subtask 2

Matrix exponentiation no longer works here since the number can be quite large: we can have r (the length after one operation) upto 9\cdot 10^4 which is too much for \mathcal{O}(r^3 \log K) to work.

Instead, let’s use the fact that we don’t actually care about the entire suffix sum: we only want its first element after K iterations.

From the fact that we had a linear recurrence, we know that there must exist some coefficients c_1, c_2, \ldots, c_r such that the final answer is \sum_{i=1}^r c_i \cdot A_i.
Let’s try to find these coefficients.

If you try writing out what these coefficients are for a few small values of K, you’ll notice something rather interesting: they’re nothing but binomial coefficients!
In fact, the coefficients (when rotated 45^o) essentially just form Pascal’s triangle.
Some intuition for why this happens and related discussion can be found here.

At any rate, we just need to compute some binomial coefficients; in particular, you’ll get something like c_i = \binom{K+i-2}{i-1}.

The numerator of each coefficient is quite large, so standard methods of computing them won’t work.
The denominator is \lt r, and this allows us to compute a single coefficient in \mathcal{O}(r), but this is still a \mathcal{O}(r^2) solution overall, which is too slow.

Instead, let’s use the fact that the binomial coefficients are of a special type.
Suppose we knew \binom{K+i-2}{i-1}. Can we get \binom{K+(i+1)-2}{(i+1)-1} = \binom{K+i-1}{i} from it?

Yes we can!

Let’s write out the factorial expansions of the coefficients. We have:
\displaystyle \binom{K+i-2}{i-1} = \frac{(K+i-2)!}{(i-1)! (K-1)!}
\displaystyle \binom{K+i-1}{i} = \frac{(K+i-1)!}{i! (K-1)!}

In particular, multiplying the first one by (K+i-2) and dividing it by i bring us to the second.

This allows us to move from one coefficient to the other in \mathcal{O}(\log {MOD}) (for division, though you can also do \mathcal{O}(1) by precomputing all inverses).
In particular, slower languages such as Python might require precomputing of inverses.

So, we have a solution in \mathcal{O}(r) or \mathcal{O}(r\log {MOD}), which is good enough since r \leq 9\cdot 10^4.


\mathcal{O}(\log N) per testcase.


Setter's code (C++)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
ll power(ll x,ll y){
    ll res=1;
    if(x==0)return 0;
    return res;
int main() {
	ll T;
	cin >> T;
	    ll k;
	    string s;
	    cin >> s >> k;
	    ll x=s.size();
	    for(ll i=0;i<x;i++)for(ll j=0;j<(ll)(s[x-1-i]-'0');j++)pows.push_back(i+1);
	    ll y=pows.size();
	    ll ans=0;
	    ll c=1;
	    for(ll i=0;i<y;i++){
	    cout << ans << endl;
	return 0;
Tester's code (C++)
#include <bits/stdc++.h>
#define mod 998244353
#define ll long long int
using namespace std;

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

int main() {
	int t;
	cin >> t;
	while(t--) {
	    string s;
	    cin >> s;
	    int k;
	    cin >> k;
	    if(k == 0) cout << s.size() << "\n";
	    else {
	        vector<long long int> v;
	        for(int i = 0; i < s.size(); i++) {
	            for(int j = 0; j < s[i] - '0'; j++) {
	                v.push_back(s.size() - i);
	        ll ans = 0, now = 1;
	        for(int i = 0; i < v.size(); i++) {
	            ans += (v[i]*now)%mod;
	            ans %= mod;
	            now *= (k + i);
	            now %= mod;
	            now *= mpow(i + 1, mod - 2);
	            now %= mod;
	        cout << ans << "\n";
	return 0;
Editorialst's code (Python)
mod = 998244353
maxn = 10 ** 6 + 10
invs = [1] * maxn
for i in range(2, maxn): invs[i] = (mod - (mod // i) * invs[mod%i])%mod

t = int(input())
for _ in range(t):
	n, k = input().split()
	k = int(k)
	if k == 0:
	pows = []
	for i in range(len(n)):
		times = ord(n[-1-i]) - ord('0')
		for j in range(times): pows.append(i+1)
	ans, coef, n = 0, 1, len(pows)
	for i in range(n):
		ans += pows[n-1-i] * coef
		coef = (coef * (k + i) * invs[i+1]) % mod
	print(ans % mod)

After taking the input string ‘s’ ,

vector v;
for(int i = 0; i < s.size(); i++) {
for(int j = 0; j < s[i] - ‘0’; j++) {
v.push_back(s.size() - i) ;

I am unable to understand this step , can anyone explain what is being done here and what is this for loop of j and what does (s[i] - ‘0’) mean …?? and what exactly the vector is storing…??

See the line

in the editorial.

Those lines simply perform the operation once on the number N and store the lengths of the resulting powers of 10 (which are the values k_1, k_2, \ldots, k_r mentioned in the editorial).
For example if N = 132 you would get v = [3, 2, 2, 2, 1, 1].

s[i] - '0' simply gives the digit value of the character s[i], basically it converts

'0' -> 0, '1' -> 1, ..., '9' -> 9

because that’s what you need to count the number of times some power of 10 appears in N.