Page Contents
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
- Random OR Solution Codechef
- Digit Multiplication By K Solution Codechef
- Remove Adjacent Solution Codechef
- Bitwise Blend Solution Codechef
- Binary Base Basics Solution Codechef
- N Queens Puzzle Solved ! Solution Codechef
- Chef and the Hair Salon Solution Codechef
January Long Challenge 2022 Solution
- TCS Examination EXAMTIME Solution Codechef
- Chef and Fixed Deposits MINFD Solution Codechef
- Crying Colours CRYCOLR Solution Codechef
- Power Sum POWSUM Solution Codechef
- Sum and OR SUMANDOR Solution Codechef
- Tree Master TRMT Solution Codechef
- Array Partition ARRPART Solution Codechef
- Keplers Law KEPLERSLAW Solution
- Covid Spread COVSPRD Solution
- Prime in a binary string PINBS Solution
- Retrieve back the Array XORED Solution
- Chef and Riffles RIFFLES Solution
- Sequence Master MASTER Solution
- Generating Cycles GENECYC Solution