matrix
A dense rows x cols matrix stored flat in row-major order.
Generated from spec/std/matrix.cp by cpl doc --format json.
Mat
pub struct Mat<T>A dense rows x cols matrix stored flat in row-major order.
Mat.new
fn new<R, C, S>(a: [R, C]T, over: ?S = None) -> Mat<T>A matrix from a 2-D table, multiplied under over (default Semiring(+, *)):
Mat(over: Semiring(min, +), d). m * m2, pow(m, k) and a SegTree(*, ...) of
matrices all use it. O(rows * cols).
Row i is R's i-th position and column j is C's j-th, so get(i, j) reads
a[R.nth(i), C.nth(j)]; the matrix has |R| rows and |C| columns. The keys are not kept.
- cost: O(rows * cols) time and space
- empty: a matrix with zero rows or columns
- traps: never
Examples:
domain R = 0..2; domain C = 0..3; Mat([R, C] (r, c) => 10 * Int(r) + Int(c)).get(1, 2) == 12
Mat.filled
fn filled<S>(rows: Int, cols: Int, fill: T, over: ?S = None) -> Mat<T>A rows x cols matrix with every entry fill, multiplied under over (default
Semiring(+, *)).
- cost: O(rows * cols) time and space
- traps: when
rows < 0orcols < 0
Examples:
Mat<Int>.filled(2, 3, 7).get(1, 2) == 7
Mat.zeros
fn zeros(rows: Int, cols: Int) -> Mat<T>A rows x cols matrix of T.zero.
- cost: O(rows * cols) time and space
- traps: when
rows < 0orcols < 0
Examples:
Mat<Int>.zeros(2, 3).get(1, 2) == 0
Mat.identity
fn identity(n: Int) -> Mat<T>The n x n identity matrix: T.one on the diagonal, T.zero elsewhere.
- cost: O(n^2) time and space
- traps: when
n < 0
Examples:
let m = Mat<Int>.identity(3); m.get(1, 1) == 1 and m.get(1, 2) == 0
Mat.from_flat
fn from_flat(rows: Int, cols: Int, data: List<T>) -> Mat<T>Build a rows x cols matrix from a flat row-major list of length rows * cols: entry (r, c)
is data[r * cols + c].
- cost: O(rows * cols) time and space
- empty: a matrix with zero rows or columns when
datais empty - traps: when
rows < 0,cols < 0ordata.len != rows * cols
Examples:
Mat<Int>.from_flat(2, 3, [1, 2, 3, 4, 5, 6]).get(1, 0) == 4
Mat.from_rows
fn from_rows(grid: List<List<T>>) -> Mat<T>Build a matrix from a list of equal-length rows: grid[r][c] is entry (r, c).
- cost: O(rows * cols) time and space
- empty:
[]gives the0 x 0matrix - traps: when the rows differ in length
Examples:
Mat<Int>.from_rows([[1, 2], [3, 4]]).get(1, 0) == 3
Mat.get
fn get(self, r: Int, c: Int) -> TThe entry at (r, c), 0-based.
- cost: O(1)
- traps: when
ris not in0..rowsorcis not in0..cols
Examples:
Mat<Int>.from_rows([[1, 2], [3, 4]]).get(0, 1) == 2
Mat.set
fn set(mut self, r: Int, c: Int, val: T)Set the entry at (r, c) to val.
- cost: O(1)
- traps: when
ris not in0..rowsorcis not in0..cols
Examples:
var m = Mat<Int>.zeros(2, 2); m.set(1, 0, 5); m.get(1, 0) == 5
Mat.at
fn at(self, r: Int, c: Int) -> lends mut TThe entry at (r, c), lent in place: m.at(i, j) += x.
- cost: O(1)
- traps: when
ris not in0..rowsorcis not in0..cols
Examples:
var m = Mat<Int>.identity(2); m.at(0, 0) += 4; m.get(0, 0) == 5
Mat.transpose
fn transpose(self) -> Mat<T>The transpose, a new cols x rows matrix with entry (c, r) equal to self's (r, c).
- cost: O(rows * cols) time and space
- traps: never
Examples:
Mat<Int>.from_rows([[1, 2, 3], [4, 5, 6]]).transpose().get(2, 1) == 6
Mat.mul_vec
fn mul_vec(self, v: List<T>) -> List<T>The matrix-vector product self * v under the matrix's semiring: entry r folds
get(r, c) * v[c] over c with the semiring's addition.
- cost: O(rows * cols) time, O(rows) space
- empty:
rowscopies of the semiring's zero whencols == 0 - order: indexed by row
- traps: when
v.len != cols
Examples:
Mat<Int>.from_rows([[1, 2], [3, 4]]).mul_vec([1, 1]) == [3, 7]
Mat.product
fn product(n: Int) -> Monoid<Mat<T>>The matrix-multiplication monoid for n x n matrices (usable in SegTree): identity
Mat.identity(n), op *, which is associative but not commutative.
- cost: O(n^2) time and space (for the identity)
- traps: when
n < 0
Examples:
let m = Mat<Int>.product(2); m.op(m.id, Mat<Int>.from_rows([[1, 2], [3, 4]])).get(1, 1) == 4
Mat.det
fn det(self) -> TThe determinant over an exact field (such as Mod<P> for prime P), by Gaussian elimination.
The 0 x 0 determinant is T.one.
- cost: O(n^3) time, O(n^2) space
- traps: when the matrix is not square, or an inverse it needs does not exist (a non-field
T)
Examples:
Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).det() == Mod<7>(5)Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).det() == Mod<7>(0)
Mat.rank
fn rank(self) -> IntThe rank over an exact field: the number of pivots elimination finds.
- cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
- empty: zero
- traps: never for a field
T
Examples:
Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).rank() == 1
Mat.solve_space
fn solve_space(self, b: List<T>) -> ?(List<T>, List<List<T>>)Solve self * x = b over an exact field. Returns (particular, nullspace_basis) or None.
Every solution has the form particular + sum(c_i * basis[i]). O(rows * cols * min(rows, cols)).
particular is the solution with every free variable zero (what solve returns). The basis
has one vector per free (non-pivot) column of the reduced row echelon form, in increasing
column order; the vector for free column f has 1 at f, 0 at the other free columns,
and whatever the pivot columns need. It is empty when the solution is unique.
- cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
- empty: with
cols == 0,Some(([], []))whenbis all zero, elseNone - order: basis vectors by increasing free column
- traps: when
b.len != rows
Examples:
Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve_space([1, 2]) == Some(([Mod<7>(1), Mod<7>(0)], [[Mod<7>(5), Mod<7>(1)]]))Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve_space([1, 0]) == None
Mat.solve
fn solve(self, b: List<T>) -> ?List<T>Solve self * x = b over an exact field. Returns one solution (free variables 0) or None.
The solution is solve_space(b)'s particular one: each free (non-pivot) column's variable is
zero.
- cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
- empty: with
cols == 0,Some([])whenbis all zero, elseNone - order: indexed by column (variable)
- traps: when
b.len != rows
Examples:
Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).solve([5, 6]) == Some([Mod<7>(3), Mod<7>(1)])Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve([1, 0]) == None
Mat.inverse
fn inverse(self) -> ?Mat<T>The multiplicative inverse of a square matrix over an exact field, or None if singular, by
Gauss-Jordan elimination.
- cost: O(n^3) time, O(n^2) space
- empty: the
0 x 0matrix is its own inverse - traps: when the matrix is not square
Examples:
let inv = Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).inverse()!; inv.get(0, 0) == Mod<7>(5) and inv.get(1, 1) == Mod<7>(3)Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).inverse() == None
Mat.rref
fn rref(self) -> (mat: Mat<T>, rank: Int, pivots: List<Int>)The reduced row echelon form (rref_mat, rank, pivot_cols) over a field. Every pivot is
T.one, every other entry of a pivot column is zero, the nonzero rows come first, and the
rank pivot columns are listed in increasing order. The RREF is unique, so so is the result.
- cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
- empty: rank zero, no pivots
- order: pivot columns increasing
- traps: never for a field
T
Examples:
let (mat: e, rank: k, pivots: p) = Mat<Mod<7>>.from_rows([[2, 4], [1, 2]]).rref(); k == 1 and p == [0] and e.get(0, 1) == Mod<7>(2) and e.get(1, 1) == Mod<7>(0)
Mat.det_mod
fn det_mod(self, m: Int) -> IntThe determinant modulo any (possibly composite) m >= 1, in 0..m, by Euclidean (gcd-style)
row elimination, so no inverse is needed. Entries are reduced modulo m first, negative ones
included.
- cost: O(n^3 log m)
- empty:
1 % mfor the0 x 0matrix - traps: when the matrix is not square or
m < 1
Examples:
Mat<Int>.from_rows([[1, 2], [3, 4]]).det_mod(6) == 4Mat<Int>.from_rows([[2, 0], [0, 3]]).det_mod(6) == 0
Mat.char_poly
fn char_poly(self) -> List<T>The characteristic polynomial det(xI - self), lowest degree first, via Hessenberg reduction:
n + 1 coefficients, the last one T.one.
- cost: O(n^3) time, O(n^2) space
- empty:
[T.one]for the0 x 0matrix - order: coefficient of
x^0first - traps: when the matrix is not square
Examples:
Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).char_poly() == [Mod<7>(5), Mod<7>(2), Mod<7>(1)]
Mat.pfaffian
fn pfaffian(self) -> TThe Pfaffian of an even-order skew-symmetric matrix over a field, with the sign convention
pf([[0, a], [-a, 0]]) == a; pf(A)^2 == det(A). Only the entries above the diagonal are read;
skew-symmetry is not checked.
- cost: O(n^3) time, O(n^2) space
- empty:
T.onefor the0 x 0matrix - traps: when the matrix is not square or
nis odd
Examples:
Mat<Mod<7>>.from_rows([[0, 3], [4, 0]]).pfaffian() == Mod<7>(3)
Mat.adjugate
fn adjugate(self) -> Mat<T>The adjugate matrix adj(self), the transpose of the cofactor matrix, so
self * adj(self) == det(self) * I. Defined even when rank == n - 1 (and zero when
rank < n - 1).
- cost: O(n^3) time, O(n^2) space
- empty: the
0 x 0matrix - traps: when the matrix is not square
Examples:
let a = Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).adjugate(); a.get(0, 0) == Mod<7>(4) and a.get(0, 1) == Mod<7>(5)Mat<Mod<7>>.from_rows([[5]]).adjugate().get(0, 0) == Mod<7>(1)
Mat<T>
impl Add for Mat<T>Mat<T>.add
fn add(a, b)Mat<T>
impl Sub for Mat<T>Mat<T>.sub
fn sub(a, b)Mat<T>
impl Mul for Mat<T>Mat<T>.mul
fn mul(a, b)Mat<T>
impl Pow for Mat<T>Mat<T>.pow
fn pow(a, e: Int) -> Mat<T>XorBasis
pub struct XorBasisLinear basis over GF(2) for non-negative 63-bit integers (0 <= x < 2^63).
Every operation is O(W) where W <= 63 (merge is O(W * rank)).
XorBasis.new
fn new() -> XorBasisAn empty basis of rank 0, whose span is {0}.
- cost: O(W)
- traps: never
Examples:
XorBasis().rank == 0
XorBasis.rank
fn rank(self) -> IntThe number of linearly independent vectors in the basis: the span has 2^rank elements.
- cost: O(1)
- traps: never
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.add(3); b.rank == 2
XorBasis.add
fn add(mut self, x: Int) -> BoolInsert x >= 0 into the basis. Returns true iff the rank increased, that is, iff x was not
already in the span (0 never is new). The basis is kept fully reduced: no vector has another
vector's highest bit set.
- cost: O(W)
- traps: when
x < 0
Examples:
var b = XorBasis(); let p = b.add(6); let q = b.add(5); let r = b.add(3); p and q and not rnot XorBasis().add(0)
XorBasis.reduce
fn reduce(self, x: Int) -> IntReduce x >= 0 against the basis: the minimum of x ^ s over s in the span, which is 0 iff
x is in the span.
- cost: O(W)
- traps: when
x < 0
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.reduce(4) == 1 and b.reduce(3) == 0
XorBasis.contains
fn contains(self, x: Int) -> BoolWhether x >= 0 is a XOR-combination of basis vectors: reduce(x) == 0.
- cost: O(W)
- traps: when
x < 0
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.contains(3) and not b.contains(4)
XorBasis.max_xor
fn max_xor(self, init: Int = 0) -> IntThe maximum value of init ^ s over all s in the span.
- cost: O(W)
- ties: None possible; the maximum value is unique
- traps: when
init < 0
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.max_xor() == 6 and b.max_xor(1) == 7
XorBasis.min_xor
fn min_xor(self, init: Int = 0) -> IntThe minimum value of init ^ s over all s in the span: the same as reduce(init), and 0 for
the default init.
- cost: O(W)
- ties: None possible; the minimum value is unique
- traps: when
init < 0
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.min_xor(4) == 1 and b.min_xor() == 0
XorBasis.kth
fn kth(self, k: Int) -> ?IntThe 0-indexed k-th smallest value in the span, or None if k < 0 or k >= 2^rank. kth(0)
is 0, and kth over 0..2^rank is strictly increasing and lists the whole span.
- cost: O(W^2)
- empty: only
kth(0) == Some(0)for an empty basis - ties: None possible; span values are distinct
- traps: never
Examples:
var b = XorBasis(); b.add(6); b.add(5); [b.kth(k) for k in 0..5] == [Some(0), Some(3), Some(5), Some(6), None]
XorBasis.merge
fn merge(mut self, o: XorBasis)Merge another basis into self, so self spans the union of both spans; o is unchanged.
- cost: O(W * o.rank)
- traps: never
Examples:
var a = XorBasis(); a.add(6); var b = XorBasis(); b.add(8); a.merge(b); a.rank == 2 and a.contains(14)
XorBasis.monoid
fn monoid() -> Monoid<XorBasis>The monoid under basis merge (usable in SegTree): identity the empty basis, op the merged
basis. Commutative and idempotent on spans.
- cost: O(W) (for the identity)
- traps: never
Examples:
let m = XorBasis.monoid(); m.id.rank == 0
XorBasis.basis_vecs
fn basis_vecs(self) -> List<Int>The independent basis vectors currently stored, fully reduced (no vector has another's highest bit set), so the list depends only on the span. One vector per rank.
- cost: O(W) time and space
- empty:
[] - order: decreasing (by highest set bit)
- traps: never
Examples:
var b = XorBasis(); b.add(6); b.add(5); b.basis_vecs() == [5, 3]
XorBasis.intersect
fn intersect(self, o: XorBasis) -> XorBasisA new basis spanning the intersection of the two GF(2) vector subspaces.
- cost: O(W^2)
- traps: never
Examples:
var a = XorBasis(); a.add(6); a.add(5); var b = XorBasis(); b.add(3); b.add(8); let c = a.intersect(b); c.rank == 1 and c.contains(3)
MatPow
pub struct MatPow<T>O(n^3 log max_exp) build, O(n^2 log e) query. Precomputed binary powers of a square matrix
for fast multi-query A^e * v.
MatPow.new
fn new(a: Mat<T>, max_exp: Int) -> MatPow<T>Precompute a^(2^k) for every k with 2^k <= max_exp, multiplied under a's semiring.
- cost: O(n^3 log max_exp) time, O(n^2 log max_exp) space
- traps: when
ais not square ormax_exp < 0
Examples:
let p = MatPow(Mat<Int>.from_rows([[1, 1], [1, 0]]), 10); p.apply_pow(5, [1, 0]) == [8, 5]
MatPow.apply_pow
fn apply_pow(self, e: Int, v: List<T>) -> List<T>Compute a^e * v for 0 <= e <= max_exp, as matrix-vector products with the stored powers
for the set bits of e. e == 0 returns v.
- cost: O(n^2 log e) time, O(n) space
- empty:
vitself whene == 0 - order: indexed by row
- traps: when
eis not in0..=max_exporv.len != n
Examples:
let p = MatPow(Mat<Int>.from_rows([[1, 1], [1, 0]]), 10); p.apply_pow(0, [1, 0]) == [1, 0]
BitMat
pub struct BitMat(rows: Int, cols: Int)O(n * m / 64) storage. Bit-packed dense matrix over GF(2) with word-parallel elimination.
BitMat.new
fn new(rows: Int, cols: Int) -> BitMatA zero GF(2) matrix of rows x cols, one bit per entry.
- cost: O(rows * cols / 64) time and space
- traps: when
rows < 0orcols < 0
Examples:
BitMat(2, 3).rank() == 0
BitMat.identity
fn identity(n: Int) -> BitMatThe n x n GF(2) identity matrix.
- cost: O(n^2 / 64) time and space
- traps: when
n < 0
Examples:
BitMat.identity(3).get(1, 1) and not BitMat.identity(3).get(1, 2)
BitMat.get
fn get(self, r: Int, c: Int) -> BoolRead bit (r, c).
- cost: O(1)
- traps: when
ris not in0..rowsorcis not in0..cols
Examples:
var m = BitMat(2, 2); m.set(0, 1, true); m.get(0, 1) and not m.get(1, 0)
BitMat.set
fn set(mut self, r: Int, c: Int, v: Bool)Write bit (r, c).
- cost: O(1)
- traps: when
ris not in0..rowsorcis not in0..cols
Examples:
var m = BitMat(2, 2); m.set(0, 1, true); m.set(0, 1, false); not m.get(0, 1)
BitMat.det
fn det(self) -> BoolThe determinant over GF(2): true iff the matrix is invertible. The 0 x 0 determinant is
true.
- cost: O(n^3 / 64)
- traps: when the matrix is not square
Examples:
var m = BitMat.identity(2); m.set(0, 1, true); m.det()var m = BitMat(2, 2); m.set(0, 0, true); m.set(1, 0, true); not m.det()
BitMat.rank
fn rank(self) -> IntThe rank over GF(2).
- cost: O(rows * cols * min(rows, cols) / 64)
- empty: zero
- traps: never
Examples:
var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.rank() == 1
BitMat.solve
fn solve(self, b: List<Bool>) -> ?List<Bool>Any solution to self * x == b over GF(2), or None: the one with every free (non-pivot)
variable false, as in Mat.solve.
- cost: O(rows * cols * min(rows, cols) / 64)
- empty: with
cols == 0,Some([])whenbis allfalse, elseNone - order: indexed by column (variable)
- traps: when
b.len != rows
Examples:
var m = BitMat.identity(2); m.set(0, 1, true); m.solve([true, true]) == Some([false, true])var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.solve([true, false]) == None
BitMat.solve_space
fn solve_space(self, b: List<Bool>) -> ?(x0: List<Bool>, basis: List<List<Bool>>)One solution x0 and a nullspace basis over GF(2), or None. x0 is solve(b)'s solution;
the basis has one vector per free column, in increasing column order, with true at that
column and false at the other free columns, as in Mat.solve_space.
- cost: O(rows * cols * min(rows, cols) / 64)
- empty: with
cols == 0,Some(([], []))whenbis allfalse, elseNone - order: basis vectors by increasing free column
- traps: when
b.len != rows
Examples:
var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.solve_space([true, true]) == Some((x0: [true, false], basis: [[true, true]]))
BitMat.inverse
fn inverse(self) -> ?BitMatThe inverse of a square GF(2) matrix, or None when it is singular.
- cost: O(n^3 / 64)
- empty: the
0 x 0matrix - traps: when the matrix is not square
Examples:
var m = BitMat.identity(2); m.set(0, 1, true); let inv = m.inverse()!; inv.get(0, 1) and inv.get(1, 1) and not inv.get(1, 0)
BitMat.mul
fn mul(self, o: BitMat) -> BitMatThe matrix product self * o over GF(2) (AND for multiply, XOR for add).
- cost: O(rows * cols * o.cols / 64)
- traps: when
self.cols != o.rows
Examples:
var m = BitMat.identity(2); m.set(0, 1, true); let p = m.mul(m); not p.get(0, 1) and p.get(0, 0)
PrefixXorBasis
pub struct PrefixXorBasisO(62) per push and query. Online prefix linear basis answering subarray XOR queries over any range r.
PrefixXorBasis.new
fn new() -> PrefixXorBasisAn empty prefix XOR basis, with no positions pushed.
- cost: O(1)
- traps: never
Examples:
PrefixXorBasis().rank(0..0) == 0
PrefixXorBasis.push
fn push(mut self, x: Int)Append x at the next position (0, 1, ...), keeping for each bit the basis vector with the
rightmost source index, so any subarray's span reads off the vectors whose index lies in it.
- cost: O(62) time and space
- traps: when
x < 0orx >= 2^62
Examples:
var p = PrefixXorBasis(); p.push(6); p.push(5); p.rank(0..2) == 2
PrefixXorBasis.max_xor
fn max_xor(self, r: Range<Int>, init: Int = 0) -> IntThe maximum init ^ s for s in the span of the values at positions r.
- cost: O(62)
- empty:
init(the span of nothing is{0}) - ties: None possible; the maximum value is unique
- traps: when
ris non-empty and reaches outside0..len, orinit < 0
Examples:
var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.max_xor(1..3) == 6 and p.max_xor(2..3) == 3
PrefixXorBasis.contains
fn contains(self, r: Range<Int>, x: Int) -> BoolWhether x is in the span of the values at positions r.
- cost: O(62)
- empty:
trueonly forx == 0 - traps: when
ris non-empty and reaches outside0..len, orx < 0
Examples:
var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.contains(1..3, 6) and not p.contains(1..2, 3)
PrefixXorBasis.rank
fn rank(self, r: Range<Int>) -> IntThe rank (dimension) of the span of the values at positions r.
- cost: O(62)
- empty: zero
- traps: when
ris non-empty and reaches outside0..len
Examples:
var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.rank(0..3) == 2 and p.rank(2..3) == 1