Matrix

4 posts

Matrix #1 April 28, 2026 17 min read

Matrix Fast Power — Linear Recurrence, DP Semirings & Kitamasa

Matrix fast power for linear recurrences (4 patterns), 4 semiring templates (count/bool/min-plus/max-plus), matrix+segment tree for range-add Fibonacci queries, Kitamasa O(k²logn) and NTT O(k log²k logn).

#math #matrix #fast-power #linear-recurrence #dp

Matrix #2 April 28, 2026 15 min read

Gaussian Elimination — Real, Mod, Mod-2, Incremental

Gauss elimination: real/mod/mod-2 templates (solve, det, inv, rank); incremental online RREF; Extended Lights Out, CF 1344F abstract GF(2) modelling, 2024 ICPC Kunming interactive tree queries.

#math #matrix #gaussian-elimination #linear-algebra #gf2

Matrix #3 April 28, 2026 8 min read

Linear Basis (XOR Basis) & Simplex Method

XOR linear basis: full template with kth, range basis, normalisation; Nowcoder median example; CF 1101G prefix-XOR rank; gym 104768 C XOR-divisibility; Simplex LP solver.

#math #matrix #linear-basis #xor #gf2

Matrix #4 April 28, 2026 6 min read

Matrix Problems — Fibonacci Subarray Sums, Gaussian Elimination & Expected Value

Hard matrix problems: Fibonacci squared subarray sum with segment-tree 4-tuple and companion matrix; cycle-decomposition partition state space for random-swap sorting, first-step analysis, and Gaussian elimination.

#math #matrix #segment-tree #gaussian-elimination #expected-value