Discussion @ 1013. K-based Numbers. Version 3 @ Timus Online Judge

Myrcella Can anybody tell me the algorithm to solve this question? [3] // Problem 1013. K-based Numbers. Version 3 18 Aug 2018 10:21

I have solved 1009&1012 using dp. My algorithm is O(n). Obviously it can't pass this problem's test. I think maybe there are some ways to make it quicker but I can't figure out. When I was searching in internet for solutions, I found that they are all for 1012. I'm a Junior high school students and my math is poor (for this question) TAT. Can anybody help me?? THx in advance.

L0ve Re: Can anybody tell me the algorithm to solve this question? [2] // Problem 1013. K-based Numbers. Version 3 18 Aug 2018 10:59

You should try to look up on the Internet how to find Fibonacci number with matrix exponentiation. The level of material should be accessible to a high school student if you are willing to spend couple of hours getting comfortable with new notations/definitions. There's not much theory behind this. You also need to know how to do fast exponentiation (i.e. in O(lon n) instead of O(n)) and use Long arithmetics (like BigInteger in Java).

Myrcella Re: Can anybody tell me the algorithm to solve this question? // Problem 1013. K-based Numbers. Version 3 18 Aug 2018 11:40

Thanks! Luckily I have known about knoledge about quickpow. Very helpful segguestion!XD

Myrcella Re: Can anybody tell me the algorithm to solve this question? // Problem 1013. K-based Numbers. Version 3 18 Aug 2018 13:05

Thank you again. I think I gain a lot after solving this question! I nearly knew nothing about matrix in the past.

Discussion of Problem 1013. K-based Numbers. Version 3