-synx-'s blog

By -synx-, history, 4 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

»
4 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