Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

[Timus 1766] How to apply Gaussian elimination?

Revision en1, by sheaf, 2019-02-09 19:52:12

Hello everyone. I've just solved Timus 1766. The solution has something to do with random walks and Markov chains (not going to describe it). The problem reduces to computing Av. I have solved it by raising a certain matrix A to sufficiently big power (2120 in my case). After reading problem discussions I've found out it could be computed using Gaussian elimination. Can anybody explain what does Gaussian elimination have to do with raising matrix to an infinite power?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sheaf 2019-02-09 19:52:12 599 Initial revision (published)