Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Fast matrix multiplication does not need to be hard

Revision en1, by i_love_sqrt_decomp, 2025-08-26 05:01:46

I have done a matrix multiplication program that runs ~50x faster than plain naive implementation and ~3x faster than IKJ-order with modular tricks in just 55 lines of code.

Typically, to get this kind of speed, you would have to spend 300+ lines of code for a Strassen implementation.

Here is the link: https://judge.yosupo.jp/submission/310249. A lot of the code was based on https://codeforces.me/blog/entry/101655, aside from the tmp part.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English i_love_sqrt_decomp 2025-08-26 07:48:48 40
en2 English i_love_sqrt_decomp 2025-08-26 05:03:56 27 Tiny change: 'd of speed, you woul' -> 'd of speed (top 4 on Library Checker), you woul'
en1 English i_love_sqrt_decomp 2025-08-26 05:01:46 503 Initial revision (published)