SpOJ — BFLAG

Revision en1, by color_me_red, 2017-07-04 18:05:11

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!

Tags spoj, #matrix exponentialtion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English color_me_red 2017-07-04 18:05:11 606 Initial revision (published)