PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kulyash
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093
DIFFICULTY:
2535
PREREQUISITES:
Combinatorics
PROBLEM:
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
EXPLANATION:
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}
\vdots
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)!}
and
\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.
TIME COMPLEXITY:
\mathcal{O}(\log N) per testcase.
CODE:
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;
x=x%mod;
if(x==0)return 0;
while(y>0){
if(y&1)res=(res*x)%mod;
y=y>>1;
x=(x*x)%mod;
}
return res;
}
int main() {
ll T;
cin >> T;
while(T--){
ll k;
string s;
cin >> s >> k;
ll x=s.size();
vector<ll>pows;
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++){
ans=(ans+pows[y-1-i]*c)%mod;
c=(c*(k+i)%mod)*power(i+1,mod-2)%mod;
}
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:
print(len(str(n)))
continue
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)