### determinism's blog

By determinism, 6 years ago,

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) ?

• +9

 » 6 years ago, # |   +3 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.
•  » » 6 years ago, # ^ |   0 How can I hash (x1,x2,x3...,xn) into an integer?
•  » » » 6 years ago, # ^ |   +3 You can generate all the required vectors, sort them and then use a map. But this is a very bad way. :PI hope someone else gives you a better answer.
•  » » » 6 years ago, # ^ |   +8 An alternative form is to treat it like a number base, i.e. hash it asx_1 + mult[1] * (x_2 + mult[2] * (x_3 + ... mult[n-1] * x_n))))))) orx_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
 » 4 weeks ago, # |   0 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/