-synx-'s blog

How to solve this Fibonacci Problem — FRSKH?
By -synx-, history, 7 years ago, In English

SPOJ — FRSKH
The problem requires to efficiently compute

The constraints are:

I have solved the easier version with constraint on and same constrains on
M can be optimized using Pisano Period
N can be optimized using Fast Doubling/Matrix Exponentiation
The issue is constraint on K, which I cant figure a way to optimize. How can we resolve this issue?

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

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hello. This problem is actually harder than I thought and even algorithm is not deterministic. Here you can find editorial (page 68): http://www.bubblecup.org/Content/Media/Booklet2013.pdf

→ Reply