How to solve ITRIX12E from SPOJ?

algorithm
dps
matrix-expo
spoj

#1

I have been trying to solve ITRIX12E - R Numbers since very long unfortunately I couldn’t solve this. Can anyone please help in solving this problem.


#2

Matrix exponentiation should work i think so

Let say dp*[j] denoted the number of R-numbers of length i ending with j

So dp*[1]=dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][6]

dp*[9]=dp[i-1][2]+dp[i-1][4]+dp[i-1][8]

So we have to calculate ,sum(dp[n][j]) for all j

We can represent this with matrix :

N.                          N-1

1. |1 1 0 1 0 1 0 0 0| 1 2. |.................|. 2 3. |..................| 3 4. |..................| 4 5 = |.................|* 5 6. |.................|. 6 7. |.................|. 7 8. |.................|. 8 9. |.................|. 9

So we get a matrix ,dp[n]=X*dp[n-1]

We can expand,dp[n-1] similarly

So dp[n]=X^(n-1)*dp[1]

`


#3

How to further proceed it?

How to find it for all n <= N in the time limit?


#4

@vijju123 do u know how to correct this latex issue,in preview it was showing


#5

@vivek_1998299

dp*[1]=dp[i-1][2]+dp[i-1][4]+dp[i-1][6] …dp*[9]

Can you please explain why dp*[9] has been included and dp[i-1][1] is missing since 2 is also the prime no.


#6

dp*[9] is not included

That … means the recurrence relation for dp*[2],dp*[3] upto dp*[9]


#7

@vivek_1998299

and why dp[i-1][1] is not included in dp*[1] since here 1+1 will produce 2 which is prime no.


#8

@vivek_1998299

dp[2][1]=3
dp[2][2]=4
dp[2][3]=3
dp[2][4]=4
dp[2][5]=3
dp[2][6]=3
dp[2][7]=2
dp[2][8]=3
dp[2][9]=3

If we add them all then it becomes 28, but answer when n=2 is 30


#9

Yeah dp[i-1][1] should be there,i havemt wrote the exact equations,just written so u could get what i mean.

By the wayy for n=30,ans is 29,and in ur above case dp[2][1]=4,so ur ans is also 29

Sum of R-nos of length less than equal to 2 =4+29=33