|
|
back to boardCan anybody help? 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 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 :) My such realisation works in 0.609. 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 |
|
|
