# DIGMULK-Editorial

Author: Ashis Ghosh
Tester: Tejas Pandey
Editorialist: Daanish Mahajan

Easy Medium

# PREREQUISITES:

Binary-Exponentiation, Solving linear equations using matrices

# PROBLEM:

Given a string S of length N and an integer K, in each step we do the following:

• Initialise an empty string S'. Iterate over the characters of S in increasing order and append the string K \cdot S_i to S'.
• S = S'.

Find the length of string S modulo 1'000'000'007 after M steps.

# EXPLANATION:

Hint 1

Try writing cnt_{i + 1, j} in terms of cnt_{i, j} where cnt_{i, j} represent the count of character j in S after we have done i operations.

Hint 2

Write the linear equations you got in matrix form and try finding a relationship between cnt_M and cnt_0.

Solution

Let cnt_{i, j} represent the count of character j in S after we have done i operations.
Let F_{c, j} represent the count of character j in the string c \cdot K.
So the following equations hold:
cnt_{i + 1, j} = \sum_{c = 0}^{9} cnt_{i, c} \cdot F_{c, j}, \forall j \in [0, 9]

Writing in the form of matrices:
cnt_{i + 1} = cnt_i \cdot F where \cdot represents matrix multiplication.
Here cnt matrix is of size 1 \times 10 and F matrix is of the size 10 \times 10.

Similarly,
cnt_{i + 2} = cnt_{i + 1} \cdot F = (cnt_i \cdot F) \cdot F = cnt_i \cdot (F \cdot F) = cnt_i \cdot F^2
Therefore we can also write:
cnt_M = cnt_0 \cdot F^M

Finally answer = \sum_{j = 0}^{9} cnt_{M, j}

# COMPLEXITY ANALYSIS:

We calculate cnt_0 matrix in \mathcal{O}(N) and F matrix in \mathcal{O}(\sum_{c = 0}^{9}  length of string(c \cdot K)) = \mathcal{O}(1).
Next we calculate F ^ M with binary exponentiation in \mathcal{O}(10^3 \cdot \log_2 M) time and multiply cnt_0 and F ^ M in \mathcal{O}(1) time.

So final complexity is \mathcal{O}((10^3 \cdot \log_2 M) + N) for a single test case.

# SOLUTIONS:

Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod=1000000007;

bool test  = 1;
int n,k,m;

void multiply(int a[][10],int b[][10]){
int x[10][10] = {0};
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
for(int k = 0; k < 10; ++k){
x[i][j] += (a[i][k]*b[k][j])%mod;
x[i][j] %= mod;
}

for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
a[i][j] = x[i][j];
}

void power(int F[][10],int n){
int res[10][10] = {0};
for(int i = 0; i < 10; ++i)
res[i][i] = 1;
while(n){
if(n&1)
multiply(res,F);
n >>= 1;
multiply(F,F);
}
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
F[i][j] = res[i][j];
}

void solve(int tc = 0)
{
cin >> n >>k >> m;
assert(1<=n<=1e3);
assert(1<=k<=1e9);
assert(1<=m<=1e9);
string s;

cin >>s;
int F[10][10] = {0};
for(int i = 0; i < 10; ++i){
int p = i*k;
if(p==0){
F[0][i]++;
continue;
}
while(p){
F[p%10][i]++;
p/=10;
}
}

power(F,m);

int ans = 0;

int cnt[10] = {0};
for(int i = 0; i < n; ++i)
cnt[s[i]-'0']+=1;

for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j){
ans += (cnt[j]*F[i][j])%mod;
ans %= mod;
}

cout<<ans<<"\n";

}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
#endif
int t=1;
if(test)
cin>>t;
for(int i = 1; i <= t; ++i){
solve(i);
}
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
#define MOD 1000000007
#define SZ 10
using namespace std;

{
int res = a + b;
if(res >= MOD)
return res - MOD;
return res;
}

int mult(int a, int b)
{
long long res = a;
res *= b;
if(res >= MOD)
return res % MOD;
return res;
}

struct matrix
{
int arr[SZ][SZ];

void reset()
{
memset(arr, 0, sizeof(arr));
}

void makeiden()
{
reset();
for(int i=0;i<SZ;i++)
{
arr[i][i] = 1;
}
}

matrix operator + (const matrix &o) const
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
}
}
return res;
}

matrix operator * (const matrix &o) const
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
res.arr[i][j] = 0;
for(int k=0;k<SZ;k++)
{
res.arr[i][j] = add(res.arr[i][j] , mult(arr[i][k] , o.arr[k][j]));
}
}
}
return res;
}
};

matrix power(matrix a, int b)
{
matrix res;
res.makeiden();
while(b)
{
if(b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}

int main() {
int t;
cin >> t;
while(t--) {
int n, k, m;
cin >> n >> k >> m;
string s;
cin >> s;
matrix mat;
mat.reset();
mat.arr[0][0] = 1;
if(k == 0) for(int i = 0; i < 10; i++) mat.arr[0][i] = 1;
for(int i = 1; i < 10; i++) {
long long int now = (long long)i*k;
while(now) {
mat.arr[now%10][i]++;
now /= 10;
}
}
matrix expo = power(mat, m);
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < 10; j++)
ans = add(ans, expo.arr[j][s[i] - '0']);
}
cout << ans << "\n";
}
return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int mod = 1e9 + 7;
class Matrix {
public:
int col, row, mod;
typedef vector<ll> Row;
vector<Row> data;
Matrix(int r, int c): row(r), col(c), data(r, vector<ll>(c, 0)) {}
void initialiseIdentity(){
assert(row == col);
for(int i = 0; i < row; i++){
for(int j = 0; j < row; j++){
data[i][j] = i == j;
}
}
}
void initialiseZero(){
for(int i = 0; i < row; i++){
for(int j = 0; j < row; j++){
data[i][j] = 0;
}
}
}
};

Matrix mul(Matrix const &a, Matrix const &b){
assert(a.col == b.row);
Matrix c(a.row, b.col);
for(int i = 0; i < a.row; i++){
for(int j = 0; j < b.col; j++){
for(int k = 0; k < a.col; k++){
c.data[i][j] += a.data[i][k] * b.data[k][j] % mod;
c.data[i][j] %= mod;
}
}
}
return c;
}

Matrix mat(10, 10);

Matrix rpe(int b){
Matrix ans(10, 10);
ans.initialiseIdentity();
while(b != 0){
if(b & 1)ans = mul(ans, mat);
mat = mul(mat, mat); b >>= 1;
}
return ans;
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
int n, k, m;
string s;
while(t--){
mat.initialiseZero();
cin >> n >> k >> m;
cin >> s;
Matrix cnt(10, 1);
for(char c : s){
cnt.data[c - '0'][0]++;
}
for(int i = 0; i < 10; i++){
string s1 = to_string((ll)i * k);
for(char c : s1){
mat.data[c - '0'][i]++;
mat.data[c - '0'][i] %= mod;
}
}
Matrix ans = mul(rpe(m), cnt);
ll sum = 0;
for(vector<ll> v : ans.data)for(ll x : v)sum = (sum + x) % mod;
cout << sum << endl;
}
return 0;
}

2 Likes

Solution I solved it using DP with the concept of Binary Liftingâ€¦ We first calculate answers for power of 2 steps in logarithmic time and then we combine them to calculate for original M also in logarithmic timeâ€¦

6 Likes

Hi,
Sir Can you explain in simple terms how you calculated the digits for the power of 2 steps? At least , can you mention the resources to understand the concept?

is there any way to decrease the time complexity further
this is the link of my code:

https://www.codechef.com/viewsolution/57939621

in the video solution what is 1 * k 0 *k can any one explain?

2 Likes

I looked at it briefly, and I believe your code is linear in terms of M. That may be the main source of the slowness. The setter / testerâ€™s solution use a log M solution as follows: imagine say M = 100. You have to do the same operation 100 times. Itâ€™s faster to calculate what the EFFECT of the operation after 50 times, and then repeat it twice. In matrix form, youâ€™re trying to calculate M^100. Itâ€™s faster to do it as A = M^50 and calculate A * A.

suppose after i-1 levels
string is â†’ 12738
and k is 5
dp[i][0] = dp[i-1][0]x( number of zeroes in 0x5) + dp[i-1][1]x( number of zeroes in 1x5) + dp[i-1][2]x( number of zeroes in 2x5)+ dp[i-1][3]x( number of zeroes in 3x5) + dp[i-1][4]x( number of zeroes in 4x5) + dp[i-1][5]x( number of zeroes in 5x5) + dp[i-1][6]x( number of zeroes in 6x5) + dp[i-1][7]x( number of zeroes in 7x5) + dp[i-1][8]x( number of zeroes in 8x5) + dp[i-1][9]x( number of zeroes in 9x5)
= 0x1 + 1x0 + 1x1 + 1x0 + 0 x1 + 0x0 + 0x1 + 1x0 + 1x1 + 0x0
= 2

basically only 2 and 8 from the previous level will contribute to zeroes in the ith level, so dp[i][0] = 2

2 Likes

https://www.codechef.com/viewsolution/57983167
can anybody help me why is program is giving runtime error in hidden test case

can u help me

@hendrata if possible can i get a pseudocode i understood it but even a small pseudocode would help me greatly

Hi do you mean pseudocode for the whole program, or for just calculating A^M?

For the whole program the steps are as follows:

1. Let v be the 10x1 vector of the number of white balls in the initial condition
2. Let A be the 10x10 matrix such that, if current condition is w (10x1 matrix), then the next condition after 1 iteration is Aw. So figuring out matrix A is not hard. Think about if you only have 1 white ball of digit 1, what would the next result be? If you only have 1 white ball of digit 2? and so on.
3. Then after M iterations, the final condition is A^M * w (where the exponentiation and multiplication is done in the matrix and vector way, not per element)

The bulk of your running time will be in calculating A^M. So this is the pseudocode:
If M is even, let p = M/2. Calculate B = A^p. So A^M = B * B.
If M is odd, let p = (M-1)/2. Calculate B = A^p. So A^M = A * B * B.

So you will have to do O(log M) multiplications. Most of the TLE solutions here probably do it in O(M) multiplications, thatâ€™s why you get TLE. Each multiplication takes about 10^3 operations, so thatâ€™s why the editorial says itâ€™s O(10^3 . log M).