Digit Multiplication By K Solution Codechef

by

Digit Multiplication By K Solution Codechef

There is a strange game played in ChefLand.

The game starts with NN white balls, the ii-th of which has a power of SiSi. It is known that 0≤Si≤90≤Si≤9. On each level, a black ball with power KK hits each of the white balls. After the collision, the power of each white ball is multiplied by KK.

However, white balls are only allowed to have single-digit power. In order to maintain this, a white ball whose power contains multiple digits splits into several white balls with single-digit power, one per digit.

For example, consider a white ball with a power of 44.

  • If K=2K=2, its resulting power is 88 and it remains a single ball.
  • If K=13K=13, its resulting power is 5252, so it splits into two white balls with power 55 and 22 respectively.
  • If K=27K=27, its resulting power is 108108, so it splits into three white balls with power 11, 00, and 88 respectively.

The aim of the game is to determine the number of white balls after MM levels. Note that KK remains the same for every level.

Please help Chef win the game. Since the answer can be large, print it modulo 109+7109+7.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains three space-separated integers NN, KK, and MM.
  • The second line of each test case contains a string SS of length NN, where SiSi is the initial power of ii-th ball.

Output Format

For each test case, output in a single line the number of white balls at the end of the game, modulo 109+7109+7.

Constraints

  • 1≤T≤1001≤T≤100
  • 1≤N≤10001≤N≤1000
  • 0≤K,M≤1090≤K,M≤109

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
4 9 2
5418
5 63 3
40514
1 100000 100000
0

Sample Output 1 

14
88
1

Explanation

Test case 11:

  • Initially S=5418S=5418
  • After the 1st1st, level S=4536972S=4536972
  • After the 2nd2nd level, S=36452754816318S=36452754816318

There are 1414 white balls, so the answer is 1414.

Test case 33: After each level, S=0S=0. So, the answer is 11.

SOLUTION

Program: Digit Multiplication By K Solution in Python

import numpy as np
nmax = 1000000007
t = int(input())
for i in range(t):
    mat = np.zeros((10,10))
    mat = mat.astype(int)
    n,k,m = map(int, input().split())
    if m == 0:
        print(n)
        input()
        continue
    for j in range(10):
        for v in map(int, list(str(j*k))):
            mat[v,j] += 1
    mats = [mat]
    for j in range(int(np.log2(m))):
        mat = ([email protected])%nmax
        mats.append(mat)
    fmat = np.identity(10)
    fmat = fmat.astype(int)
    j = 0
    while m>0:
        if m%2==1:
            fmat = ([email protected][j])%nmax
        m = m//2
        j += 1
    vec = np.zeros((10,1))
    vec = vec.astype(int)
    for v in map(int, list(input())):
        vec[v,0] += 1
    outvec = ([email protected])%nmax
    print(sum(sum(outvec)%nmax))

February Long Challenge 2022 Solution

January Long Challenge 2022 Solution

Leave a Comment

15 − 2 =