I could't solve this problem, then I've read the editorial; but, I still can't understand how we convert dp states into matrices. Can someone, who knows the solution, elaborate?

PS: I know how to compute Nth power of matrix (size M*M) in `O(M^3 * log N)`

. I couldn't understand the values we are storing in the matrix and how kth matrix is used to get (k+1)th matrix.

UPD: I've coded the solution as sandeepmohanty told me, but I think that my implementation is awful. How can I improve it (especially initialising adjacency matrix) ?

Consider a state (x1, x2,.. , xn).

Here xi denotes the number of times crime i is committed % its multiplicity.

So there are a maximum of 123 states.

Now, create a graph where there is an edge from (x1,.. xi,.. xn) to (x1,.. (xi + 1) % mi,.. xn), for each i. (Basically from each state there are n edges, each edge means committing a particular crime).

Now, you can see that committing k number of crimes means traversing k edges.

So, the question now basically reduces to finding out the number of n length paths in this graph from node (0, 0,... 0) to (0, 0, .., 0).

This is a pretty standard problem whose answer is simply [0][0] element in the adjacency matrix of this graph exponentiated to n-1.

How can I hash (x1,x2,x3...,xn) into an integer?

You can generate all the required vectors, sort them and then use a map. But this is a very bad way. :P

I hope someone else gives you a better answer.

An alternative form is to treat it like a number base, i.e. hash it as

x_1 + mult[1] * (x_2 + mult[2] * (x_3 + ... mult[n-1] * x_n)))))))

or

x_1 + x_2 * mult[1] + x_3 * mult[1] * mult[2] + x_4 * mult[1] * mult[2] * mult[3] + ...

I don't know if it's strictly better than what was suggested, but it's an alternative way: 9453430

Nikhil ( pa.n.ik ) might be of some help, being a criminal himself. (Rapists like you should just eat poison and die. I'm providing you with link for cyanide.) https://www.amazon.com/Industrial-Test-Systems-486812-Cyanide/dp/B00DIJ9UEM/