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.

# How to solve ITRIX12E from SPOJ?

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]

`

**arpit728**#5

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.

dp*[9] is not included

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

**arpit728**#7

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

**arpit728**#8

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

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