4 ms·
Likewise I was surprised at how trivial this seemed? My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics
by chromatin 6y ago
Likewise I was surprised at how trivial this seemed?
My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.
- murgindrag 6y agoThe "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it. It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.