Approach for the question Crime Management (codeforces 107 D)

I cannot understand how to solve this problem using matrix exponentiation and also how should i calculate the transition matrix.
And more specifically this paragraph in editorial :

“The key step to solve the problem now is to notice that each transition from the solution for the first k crimes to the solution for the first (k + 1) crimes can be seen as multiplying the vector of the current state by the transition matrix. Once all possible transitions are converted to the matrix form, the problem can be solved by raising the matrix into n-th power. Raising the matrix into large power can be done efficiently using matrix exponentiation: on some steps instead of computing Ai + 1 = Ai· A0 one can compute A2i = Ai· Ai.”

I mean what transition matrix to multiply.

Question Link:

Editorial Link:

Thanks in Advance!!

1 Like

Ohk ,i got it.

Just in case if anyone would need help,i am telling.

See there can be atmost 123 different combinations of that crimes,so lets say i calculate all of them.So combinations could be (2,1,1),(1,3,1),(0,0,0)

We want the value of (0,0,0) after n crimes.Lets say we have input for crimes as

A 3

B 3

C 3

Now lets define dp,dp(curr)(x,y,z) = dp(prev)((x-1+A)%A),(y-1+B)%B,(z-1+C)%C). ---------(1A)

So lets say to calculate dp(2,2,2)=dp(1,2,2)+dp(2,1,2)+dp(2,2,1)

Now lets hash the vectors(or number them)

Lets say (2,2,2) is 0,(1,2,2) is 1,(2,1,2) is 2 ,(2,2,1) is 3

Lets say dp(prev)(1)=3,dp(prev)(2)=4,dp(prev)(3)=1,dp(prev)(0)=1

So now lets represent 1A in matrix form


 0.  1.  2.  3

[1.  3.  4.  1]

Just to make u understand the transition matrix lets say dp(0)=dp(1)+dp(2),dp(1)=dp(2)+dp(3),dp(2)=dp(3)=0

(This is actually column transposition)

So we can have a transition matrix as


0 0 0 0
1 0 0 0
1 1 0 0
0 1 0 0

So curr = prev*trans

So this could be considered the vector after 1 crime,so after n crimes

If init is the vector after 1 crime

1 Like

Can anyone please help!!

1 Like

Any hint would be helpful!!!

1 Like