Digit Multiplication By K Solution Codechef
There is a strange game played in ChefLand. The game starts with N white balls, the i-th of which has a power of Si. It is known that 0≤Si≤9. On each level, a black ball with power K hits each of the white balls. After the collision, the power of each white ball is multiplied by K.
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 4.
- If K=2, its resulting power is 88 and it remains a single ball.
- If K=13, its resulting power is 52, so it splits into two white balls with power 5 and 2 respectively.
- If K=27, its resulting power is 108, so it splits into three white balls with power 1, 0, and 8 respectively.
The aim of the game is to determine the number of white balls after M levels. Note that K remains the same for every level.
Please help Chef win the game. Since the answer can be large, print it modulo 109+7.
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, K, and M.
- The second line of each test case contains a string S of length N, where Si is the initial power of i-th ball.
For each test case, output in a single line the number of white balls at the end of the game, modulo 109+7.
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
Test case 1:
- Initially S=5418
- After the 1st, level S=4536972
- After the 2nd level, S=36452754816318
There are 14 white balls, so the answer is 14.
Test case 3: After each level, S=0. So, the answer is 1.
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 = (mat@mat)%nmax mats.append(mat) fmat = np.identity(10) fmat = fmat.astype(int) j = 0 while m>0: if m%2==1: fmat = (fmat@mats[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 = (fmat@vec)%nmax print(sum(sum(outvec)%nmax))