Struct FrobeniusDecomposition 

struct FrobeniusDecomposition<M>
where
    M: MIntDotProduct,
{
    t: Matrix<AddMulOperation<MInt<M>>>,
    t_inv: Matrix<AddMulOperation<MInt<M>>>,
    blocks: Vec<Polynomial<M>>,
}

Fields

t: Matrix<AddMulOperation<MInt<M>>>

t_inv: Matrix<AddMulOperation<MInt<M>>>

blocks: Vec<Polynomial<M>>

Implementations

impl<M> FrobeniusDecomposition<M>

where M: MIntDotProduct,

fn pow(&self, k: usize) -> Matrix<AddMulOperation<MInt<M>>>

Examples found in repository

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

    fn pow_frobenius(self, k: usize) -> Self
    where
        M: MIntConvert<u64>,
    {
        assert_eq!(self.shape.0, self.shape.1);
        let a = self.transpose();
        let mut rng = Xorshift::new();
        let f = loop {
            if let Some(f) = frobenius_decomposition(&a, &mut rng) {
                break f;
            }
        };
        let fk = f.pow(k);
        let n = f.t.shape.0;
        if f.blocks
            .iter()
            .map(|p| (p.0.len() - 1).pow(2))
            .sum::<usize>()
            * 4
            <= n * n
        {
            let mut ft = Matrix::zeros((n, n));
            let mut first = 0;
            for p in &f.blocks {
                let d = p.0.len() - 1;
                for i in first..first + d {
                    for j in first..first + d {
                        MInt::add_scaled_assign(&mut ft[i], &f.t[j], &fk[i][j]);
                    }
                }
                first += d;
            }
            &f.t_inv * &ft
        } else {
            &(&f.t_inv * &fk) * &f.t
        }
    }