akash2504's blog

spoj upper right king (hard)
By akash2504, 12 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?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It helps you to solve.

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

    sry.... got it :) many thanks

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        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
      • »
        »
        »
        »
        8 years ago, # ^ |
          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