color_me_red's blog

By color_me_red, history, 7 years ago, In English

There is this code:

Function Find(integer n,function func) If n=1
       For i = 1 to a do func()
   Elseif n=2
       For i = 1 to b do func()
   Else Find(n-1,Find(n-2,func))

Function Main
   Find(n,funny)

With given values of n, a, b and a modulus p, the question asks to output the number of times func() will be called. n can be upto 10^9. The direct recurrence would be f[n] = f[n-2]*(f[n-1] + 1) with base cases for 1, 2 I think. But since this isn't a linear recurrence how can I use matrix exponentiation to solve the problem? Thanks for any help!

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