Блог пользователя knb

Solve non linear recurrence relation
Автор knb, 10 лет назад, По-английски

I have a non linear recurrence relation a(n)=(n-1)*(a(n-1)+a(n-2)).How can I calculate a(n)%MOD in O(log(n)) time? Base conditions:-a(0)=0,a(1)=1

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This is basically a recurrence for n!. (The base conditions are not mentioned but even with those, the solution will not be very different). And I dont think there is a simple way to do it in sub-linear time. :(

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Actually, the base conditions matter a lot. For example, if a0 = 1, a1 = 0, then it's a recurrence for !n (number of derangements).

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Xellos,since you are saying that base condition matters a lot,I take a(0)=1 and a(1)=0 .Can I calculate the recurrence relation in O(log(n))?

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Maybe there's some obscure algorithm that does it, I don't know. But for the purpose of solving contest problems, assume you can't.

        → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry! By solution I meant "solving the task in logN time", because there is at least one base condition in which solution takes linear time. I guess I messed up with the wordings :P

      → Ответить