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 1518. Jedi Riddle 3

Help~~How to solve it?
Posted by tob 17 Dec 2006 18:43
Can anybody help?
Re: Help~~How to solve it?
Posted by svr 27 Feb 2007 23:15
Easy solution without optimization efforts.
Use Matrix A=
[0   1  0  0  0  0]
[0   0  1  0  0  0]
[0   0  0  0  1  0]
[0   0  0  0  0  1]
[c1 c2 c3 c4 c5 c6]
Answer=[[A^(X-N)]*K][N]
Thus we must calculate pow A^(X-N)
Use famous O(lg) pow in groop of matrix
__int64 in inner calculations and int (rez)%Y as result
Re: Help~~How to solve it?
Posted by Denis Koshman 18 Jul 2008 17:33
My such solution ran for 2.9 seconds with 3 for TL. So it's still not enogh for stable solution.

I had to differentiate between M^2 and M*A matrix multiplications (the latter can be implemeted via int, +, - and >=), then it ran for 1.5 sec :)
Re: Help~~How to solve it?
Posted by Chmel_Tolstiy 18 Jul 2008 18:43
My such realisation works in 0.609.
Re: Help~~How to solve it?
Posted by Harkonnen 17 Aug 2022 11:13
This time even without optimizations on +- for fast modulus, and not using fact that matrix is sparse in those cases (so multiplication can be done at O(N^2)) - it's 0.078 sec. With these optimizations - 0.046 sec.

Edited by author 17.08.2022 11:56