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