Term

Segment-Tree

Index

All notes

2026.04.28

Matrix 17 min read

Matrix #1: 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

2026.04.28

Matrix 6 min read

Matrix #4: 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