How to solve ITRIX12E from SPOJ?

general
, , ,
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[i][j] denoted the number of R-numbers of length i ending with j

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

…

…

…

dp[i][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

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

4

@vivek_1998299

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

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

5

dp[i][9] is not included

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

6

@vivek_1998299

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

7

@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

8

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

9

How to further proceed it?

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