BlackBoxMIntMatrix

competitive::math

Trait BlackBoxMIntMatrix 

Source 
pub trait BlackBoxMIntMatrix<M>: BlackBoxMatrix<AddMulOperation<MInt<M>>>
where
    M: MIntBase,
{
    // Provided methods
    fn minimal_polynomial(&self) -> Vec<MInt<M>>
       where M: MIntConvert<u64> { ... }
    fn apply_pow<C>(&self, b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
       where M: MIntConvert<usize> + MIntConvert<u64>,
             C: ConvolveSteps<T = Vec<MInt<M>>> { ... }
    fn black_box_determinant(&self) -> MInt<M>
       where M: MIntConvert<u64> { ... }
    fn black_box_linear_equation(&self, b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>>
       where M: MIntConvert<u64> { ... }
}

Provided Methods§

Source

fn minimal_polynomial(&self) -> Vec<MInt<M>>
where M: MIntConvert<u64>,

Examples found in repository?
crates/competitive/src/math/black_box_matrix.rs (line 243)
235    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
236    where
237        M: MIntConvert<usize> + MIntConvert<u64>,
238        C: ConvolveSteps<T = Vec<MInt<M>>>,
239    {
240        assert_eq!(self.shape().0, self.shape().1);
241        assert_eq!(self.shape().1, b.len());
242        let n = self.shape().0;
243        let p = self.minimal_polynomial();
244        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
245        let mut res = vec![MInt::zero(); n];
246        for f in f {
247            for j in 0..n {
248                res[j] += f * b[j];
249            }
250            b = self.apply(&b);
251        }
252        res
253    }
254
255    fn black_box_determinant(&self) -> MInt<M>
256    where
257        M: MIntConvert<u64>,
258    {
259        assert_eq!(self.shape().0, self.shape().1);
260        let n = self.shape().0;
261        let mut rng = Xorshift::new();
262        let d: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
263        let det_d = d.iter().fold(MInt::one(), |s, x| s * x);
264        let ad = BlackBoxMatrixImpl::<AddMulOperation<MInt<M>>, _>::new(
265            self.shape(),
266            |v: &[MInt<M>]| {
267                let mut w = self.apply(v);
268                for (w, d) in w.iter_mut().zip(&d) {
269                    *w *= d;
270                }
271                w
272            },
273        );
274        let p = ad.minimal_polynomial();
275        let det_ad = if n % 2 == 0 { p[0] } else { -p[0] };
276        det_ad / det_d
277    }
278
279    fn black_box_linear_equation(&self, mut b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>>
280    where
281        M: MIntConvert<u64>,
282    {
283        assert_eq!(self.shape().0, self.shape().1);
284        assert_eq!(self.shape().1, b.len());
285        let n = self.shape().0;
286        let p = self.minimal_polynomial();
287        if p.is_empty() || p[0].is_zero() {
288            return None;
289        }
290        let p0_inv = p[0].inv();
291        let mut x = vec![MInt::zero(); n];
292        for p in p.into_iter().skip(1) {
293            let p = -p * p0_inv;
294            for i in 0..n {
295                x[i] += p * b[i];
296            }
297            b = self.apply(&b);
298        }
299        Some(x)
300    }
Source

fn apply_pow<C>(&self, b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
where M: MIntConvert<usize> + MIntConvert<u64>, C: ConvolveSteps<T = Vec<MInt<M>>>,

Source

fn black_box_determinant(&self) -> MInt<M>
where M: MIntConvert<u64>,

Examples found in repository?
crates/library_checker/src/linear_algebra/sparse_matrix_det.rs (line 14)
9pub fn sparse_matrix_det(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, k, abc: [(usize, usize, MInt998244353); k]);
13    let s = SparseMatrix::from_nonzero((n, n), abc);
14    let ans = s.black_box_determinant();
15    iter_print!(writer, ans);
16}
Source

fn black_box_linear_equation(&self, b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>>
where M: MIntConvert<u64>,

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§