akash2504's blog

spoj upper right king (hard)
By akash2504, 13 years ago, In English

can anyone suggest me how to solve http://www.spoj.pl/problems/ADV04B1

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It helps you to solve.

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    sry.... got it :) many thanks

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Please Post your approach how did you precompute??

      Post with examples it will be useful for many!

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        If you read the wolfram explanation carefully, it notes the following recurrence.

        Precalculate the inverse of n modulo 1e6 + 3 for all 1 ≤ n ≤ 1000000.

        This can be done in O(n). Then, we can precalculate all D(n) in O(n) as well.

        → Reply