Struct EchelonRow 

struct EchelonRow<M>
where
    M: MIntDotProduct,
{
    pivot: usize,
    inv: MInt<M>,
    row: Vec<MInt<M>>,
}

Fields

pivot: usize

inv: MInt<M>

row: Vec<MInt<M>>

Implementations

impl<M> EchelonRow<M>

where M: MIntDotProduct,

fn reduce(&self, row: &mut [MInt<M>])

Examples found in repository

crates/competitive/src/math/mint_matrix.rs (line 184)

fn generate_frobenius_block<M>(
    a: &Matrix<AddMulOperation<MInt<M>>>,
    mut v: Vec<MInt<M>>,
    rows: &mut Vec<EchelonRow<M>>,
    t: &mut Vec<Vec<MInt<M>>>,
) -> Polynomial<M>
where
    M: MIntDotProduct,
{
    let n = a.shape.0;
    loop {
        let mut row = vec![MInt::zero(); n + rows.len() + 1];
        let (x, c) = row.split_at_mut(n);
        x.copy_from_slice(&v);
        c[rows.len()] = MInt::one();
        for r in rows.iter() {
            r.reduce(&mut row);
        }
        if let Some(pivot) = row[..n].iter().position(|x| !x.is_zero()) {
            t.push(v);
            let u = t.last().unwrap();
            v = a.data.iter().map(|row| MInt::dot_product(u, row)).collect();
            rows.push(EchelonRow {
                pivot,
                inv: row[pivot].inv(),
                row,
            });
        } else {
            let mut p = row.split_off(n);
            while p.last().is_some_and(|x| x.is_zero()) {
                p.pop();
            }
            return Polynomial(p);
        }
    }
}