Struct Polynomial 

struct Polynomial<M>(Vec<MInt<M>>)
where
    M: MIntDotProduct;

Tuple Fields

0: Vec<MInt<M>>

Implementations

impl<M> Polynomial<M>

where M: MIntDotProduct,

fn exact_div(self, rhs: &Self) -> Option<Self>

Examples found in repository

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

fn frobenius_decomposition<M>(
    a: &Matrix<AddMulOperation<MInt<M>>>,
    rng: &mut Xorshift,
) -> Option<FrobeniusDecomposition<M>>
where
    M: MIntDotProduct + MIntConvert<u64>,
{
    let n = a.shape.0;
    let mut rows = Vec::with_capacity(n);
    let mut t = Vec::with_capacity(n);
    let mut blocks: Vec<Polynomial<M>> = Vec::new();
    while rows.len() < n {
        let s = rows.len();
        let v = (0..n).map(|_| MInt::from(rng.rand64())).collect();
        let c = generate_frobenius_block(a, v, &mut rows, &mut t);
        if rows.len() == s {
            continue;
        }
        let p = Polynomial(c.0[s..].to_vec());
        if c.0[..s].iter().any(|x| !x.is_zero()) {
            let q = c.exact_div(&p)?;
            let d = rows.len() - s;
            let mut coefficients = q.0[..s].to_vec();
            let mut shifts = Vec::with_capacity(d);
            for _ in 0..d {
                shifts.push(coefficients.clone());
                let mut first = 0;
                for block in &blocks {
                    let len = block.0.len() - 1;
                    let c = &mut coefficients[first..first + len];
                    let last = c[len - 1];
                    for j in (1..len).rev() {
                        c[j] = c[j - 1] - last * block.0[j];
                    }
                    c[0] = -last * block.0[0];
                    first += len;
                }
            }
            let shifts: Matrix<AddMulOperation<MInt<M>>> = Matrix::from_vec(shifts);
            if d < 32 {
                let (previous, current) = t.split_at_mut(s);
                for (shift, row) in shifts.data.iter().zip(current) {
                    for (factor, source) in shift.iter().zip(previous.iter()) {
                        if !factor.is_zero() {
                            MInt::add_scaled_assign(row, source, factor);
                        }
                    }
                }
            } else {
                let previous = Matrix::from_vec(t[..s].to_vec());
                let correction = &shifts * &previous;
                for (row, correction) in t[s..].iter_mut().zip(&correction.data) {
                    for (x, &y) in row.iter_mut().zip(correction) {
                        *x += y;
                    }
                }
            }
            for row in &mut rows[s..] {
                // Keep the reduced vector fixed: T_new += S*T_old gives C_old -= C_new*S.
                let (previous, current) = row.row[n..].split_at_mut(s);
                for (&x, shift) in current.iter().zip(&shifts.data) {
                    MInt::add_scaled_assign(previous, shift, &-x);
                }
            }
        }
        blocks.push(p);
    }

    let mut t_inv = vec![vec![MInt::zero(); n]; n];
    for i in (0..n).rev() {
        let row = &rows[i];
        let mut c = row.row[n..].to_vec();
        c.resize(n, MInt::zero());
        for x in &mut c {
            *x *= row.inv;
        }
        for next in &rows[i + 1..] {
            let factor = -row.row[next.pivot] * row.inv;
            if !factor.is_zero() {
                MInt::add_scaled_assign(&mut c, &t_inv[next.pivot], &factor);
            }
        }
        t_inv[row.pivot] = c;
    }
    Some(FrobeniusDecomposition {
        t: Matrix::from_vec(t),
        t_inv: Matrix::from_vec(t_inv),
        blocks,
    })
}

fn square_mod(&self, p: &Self) -> Self

Examples found in repository

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

    fn x_pow_mod(&self, k: usize) -> Self {
        let d = self.0.len() - 1;
        if d == 1 {
            return Self(vec![(-self.0[0]).pow(k)]);
        }
        let mut r = Self(vec![MInt::zero(); d]);
        r.0[0] = MInt::one();
        for bit in (0..usize::BITS - k.leading_zeros()).rev() {
            r = r.square_mod(self);
            if k >> bit & 1 != 0 {
                let x = r.0[d - 1];
                for i in (1..d).rev() {
                    r.0[i] = r.0[i - 1] - x * self.0[i];
                }
                r.0[0] = -x * self.0[0];
            }
        }
        r
    }

fn x_pow_mod(&self, k: usize) -> Self

Examples found in repository

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

    fn pow(&self, k: usize) -> Matrix<AddMulOperation<MInt<M>>> {
        let n = self.t.shape.0;
        let mut a = vec![vec![MInt::zero(); n]; n];
        let mut s = 0;
        for p in &self.blocks {
            let d = p.0.len() - 1;
            let mut c = p.x_pow_mod(k).0;
            for row in &mut a[s..s + d] {
                row[s..s + d].copy_from_slice(&c);
                let x = c[d - 1];
                for i in (1..d).rev() {
                    c[i] = c[i - 1] - x * p.0[i];
                }
                c[0] = -x * p.0[0];
            }
            s += d;
        }
        Matrix::from_vec(a)
    }