|
|
back to boardHelp~~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? 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? My such realisation works in 0.609. Re: Help~~How to solve it? 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 |
|
|