DIGMULK-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

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

DIFFICULTY:

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 add(int a, int b)
{
	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++)
			{
				res.arr[i][j] = add(arr[i][j], o.arr[i][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).