ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

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

Can anybody tell me the algorithm to solve this question?
Posted by Myrcella 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.
Re: Can anybody tell me the algorithm to solve this question?
Posted by L0ve 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).
Re: Can anybody tell me the algorithm to solve this question?
Posted by Myrcella 18 Aug 2018 11:40
Thanks! Luckily I have known about knoledge about quickpow. Very helpful segguestion!XD
Re: Can anybody tell me the algorithm to solve this question?
Posted by Myrcella 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.