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 terribleimposter 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