Problem: Devu and Locks Practice Coding Problem - CodeChef
The guide doesn’t have a solution for this, but marks it as normal under digit DP. Doesn’t this problem for full points require not only digit DP as the first step but also unbounded knapsack with binary exponentiation and FFT to make it run in O(MP^2log(M+N)) time? Is there a simpler way?
Essentially an algorithm would divide the dials into floor(N/P) blocks (we’ll handle the remainder later) and finds a matrix with x,y representing the number of ways to create a residue of x mod P using y time simply by running a normal digit dp algo.
Then in order to solve it for the general case it combines these blocks to get a new matrix with the merge operation being A[x][y]=(sum over all pairs such that a+c = x and b+d = y) B[a][b]*C[c][d].
This operation can be sped up with convolutions after fixing residues b and d.
Then we merge this array with the isolated remainder block to get an answer again using digit dp to find the matrix corresponding to it.
So our answer is just the array (M^(floor(N/P))*R)[0] where M is the matrix for a block and R is the matrix for the remainder.
I think you would want move this from normal in the module if this is the intended solution (I can’t find one online and code chef requires premium for the editorial) and tag it.