If you solve the problem row by row starting from the last one, then for every row you'll have tridiagonal matrix which can be solved much faster then standard Gauss elimination.

Good problems. I'm using hashing on C, but still get TLE on test 21.