knb's blog

Solve non linear recurrence relation
By knb, 11 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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. :(

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

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

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

      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))?

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

        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.

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

      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

      → Reply