×

# How to solve ITRIX12E from SPOJ?

 0 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. asked 13 May, 15:12 2★arpit728 683●11●49 accept rate: 10%

 0 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] ` answered 13 May, 19:27 1.3k●2●9 accept rate: 22% @vijju123 do u know how to correct this latex issue,in preview it was showing (13 May, 20:03) @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. (17 May, 10:00) arpit7282★ dp[i][9] is not included That ...... means the recurrence relation for dp[i][2],dp[i][3] upto dp[i][9] (17 May, 10:54) @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. (18 May, 08:31) arpit7282★ 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 (18 May, 09:10) arpit7282★ 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 (18 May, 10:50) showing 5 of 6 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,599
×1,071
×251
×118