Matrix

competitive::math

Struct Matrix 

Source 
pub struct Matrix<R>
where
    R: SemiRing,
{
    pub shape: (usize, usize),
    pub data: Vec<Vec<R::T>>,
    _marker: PhantomData<fn() -> R>,
}

Fields§

§shape: (usize, usize)§data: Vec<Vec<R::T>>§_marker: PhantomData<fn() -> R>

Implementations§

Source§

impl<R> Matrix<R>
where R: SemiRing,

Source

pub fn new(shape: (usize, usize), z: R::T) -> Self

Source

pub fn from_vec(data: Vec<Vec<R::T>>) -> Self

Examples found in repository?
crates/library_checker/src/linear_algebra/characteristic_polynomial.rs (line 10)
6pub fn characteristic_polynomial(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [[MInt998244353; n]; n]);
10    let p = Matrix::<AddMulOperation<_>>::from_vec(a).characteristic_polynomial();
11    iter_print!(writer, @it p);
12}
More examples
Hide additional examples
crates/competitive/src/math/matrix.rs (lines 270-272)
258    pub fn inverse(&self) -> Option<Matrix<R>> {
259        assert_eq!(self.shape.0, self.shape.1);
260        let n = self.shape.0;
261        let mut c = Matrix::<R>::zeros((n, n * 2));
262        for i in 0..n {
263            c[i][..n].clone_from_slice(&self[i]);
264            c[i][n + i] = R::one();
265        }
266        c.row_reduction(true);
267        if (0..n).any(|i| R::is_zero(&c[i][i])) {
268            None
269        } else {
270            Some(Self::from_vec(
271                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
272            ))
273        }
274    }
275
276    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
277        let n = self.shape.0;
278        if n == 0 {
279            return vec![R::one()];
280        }
281        assert!(self.data.iter().all(|a| a.len() == n));
282        for j in 0..(n - 1) {
283            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
284                self.data.swap(j + 1, x);
285                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
286                let inv = R::inv(&self[j + 1][j]);
287                let mut v = vec![];
288                let src = std::mem::take(&mut self[j + 1]);
289                for a in self.data[(j + 2)..].iter_mut() {
290                    let mul = R::mul(&a[j], &inv);
291                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
292                        R::sub_assign(a, &R::mul(&mul, src));
293                    }
294                    v.push(mul);
295                }
296                self[j + 1] = src;
297                for a in self.data.iter_mut() {
298                    let v = a[(j + 2)..]
299                        .iter()
300                        .zip(v.iter())
301                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
302                    R::add_assign(&mut a[j + 1], &v);
303                }
304            }
305        }
306        let mut dp = vec![vec![R::one()]];
307        for i in 0..n {
308            let mut next = vec![R::zero(); i + 2];
309            for (j, dp) in dp[i].iter().enumerate() {
310                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
311                R::add_assign(&mut next[j + 1], dp);
312            }
313            let mut mul = R::one();
314            for j in (0..i).rev() {
315                mul = R::mul(&mul, &self[j + 1][j]);
316                let c = R::mul(&mul, &self[j][i]);
317                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
318                    R::sub_assign(next, &R::mul(&c, dp));
319                }
320            }
321            dp.push(next);
322        }
323        dp.pop().unwrap()
324    }
325}
326
327impl<R> Index<usize> for Matrix<R>
328where
329    R: SemiRing,
330{
331    type Output = Vec<R::T>;
332    fn index(&self, index: usize) -> &Self::Output {
333        &self.data[index]
334    }
335}
336
337impl<R> IndexMut<usize> for Matrix<R>
338where
339    R: SemiRing,
340{
341    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
342        &mut self.data[index]
343    }
344}
345
346impl<R> Index<(usize, usize)> for Matrix<R>
347where
348    R: SemiRing,
349{
350    type Output = R::T;
351    fn index(&self, index: (usize, usize)) -> &Self::Output {
352        &self.data[index.0][index.1]
353    }
354}
355
356impl<R> IndexMut<(usize, usize)> for Matrix<R>
357where
358    R: SemiRing,
359{
360    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
361        &mut self.data[index.0][index.1]
362    }
363}
364
365macro_rules! impl_matrix_pairwise_binop {
366    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident $(where [$($clauses:tt)*])?) => {
367        impl<R> $imp_assign for Matrix<R>
368        where
369            R: SemiRing,
370            $($($clauses)*)?
371        {
372            fn $method_assign(&mut self, rhs: Self) {
373                self.pairwise_assign(&rhs, |a, b| R::$method_assign(a, b));
374            }
375        }
376        impl<R> $imp_assign<&Matrix<R>> for Matrix<R>
377        where
378            R: SemiRing,
379            $($($clauses)*)?
380        {
381            fn $method_assign(&mut self, rhs: &Self) {
382                self.pairwise_assign(rhs, |a, b| R::$method_assign(a, b));
383            }
384        }
385        impl<R> $imp for Matrix<R>
386        where
387            R: SemiRing,
388            $($($clauses)*)?
389        {
390            type Output = Matrix<R>;
391            fn $method(mut self, rhs: Self) -> Self::Output {
392                self.$method_assign(rhs);
393                self
394            }
395        }
396        impl<R> $imp<&Matrix<R>> for Matrix<R>
397        where
398            R: SemiRing,
399            $($($clauses)*)?
400        {
401            type Output = Matrix<R>;
402            fn $method(mut self, rhs: &Self) -> Self::Output {
403                self.$method_assign(rhs);
404                self
405            }
406        }
407        impl<R> $imp<Matrix<R>> for &Matrix<R>
408        where
409            R: SemiRing,
410            $($($clauses)*)?
411        {
412            type Output = Matrix<R>;
413            fn $method(self, mut rhs: Matrix<R>) -> Self::Output {
414                rhs.pairwise_assign(self, |a, b| *a = R::$method(b, a));
415                rhs
416            }
417        }
418        impl<R> $imp<&Matrix<R>> for &Matrix<R>
419        where
420            R: SemiRing,
421            $($($clauses)*)?
422        {
423            type Output = Matrix<R>;
424            fn $method(self, rhs: &Matrix<R>) -> Self::Output {
425                let mut this = self.clone();
426                this.$method_assign(rhs);
427                this
428            }
429        }
430    };
431}
432
433impl_matrix_pairwise_binop!(Add, add, AddAssign, add_assign);
434impl_matrix_pairwise_binop!(Sub, sub, SubAssign, sub_assign where [R: SemiRing<Additive: Invertible>]);
435
436impl<R> Mul for Matrix<R>
437where
438    R: SemiRing,
439{
440    type Output = Matrix<R>;
441    fn mul(self, rhs: Self) -> Self::Output {
442        (&self).mul(&rhs)
443    }
444}
445impl<R> Mul<&Matrix<R>> for Matrix<R>
446where
447    R: SemiRing,
448{
449    type Output = Matrix<R>;
450    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
451        (&self).mul(rhs)
452    }
453}
454impl<R> Mul<Matrix<R>> for &Matrix<R>
455where
456    R: SemiRing,
457{
458    type Output = Matrix<R>;
459    fn mul(self, rhs: Matrix<R>) -> Self::Output {
460        self.mul(&rhs)
461    }
462}
463impl<R> Mul<&Matrix<R>> for &Matrix<R>
464where
465    R: SemiRing,
466{
467    type Output = Matrix<R>;
468    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
469        assert_eq!(self.shape.1, rhs.shape.0);
470        let mut res = Matrix::zeros((self.shape.0, rhs.shape.1));
471        for i in 0..self.shape.0 {
472            for k in 0..self.shape.1 {
473                for j in 0..rhs.shape.1 {
474                    R::add_assign(&mut res[i][j], &R::mul(&self[i][k], &rhs[k][j]));
475                }
476            }
477        }
478        res
479    }
480}
481
482impl<R> MulAssign<&R::T> for Matrix<R>
483where
484    R: SemiRing,
485{
486    fn mul_assign(&mut self, rhs: &R::T) {
487        for i in 0..self.shape.0 {
488            for j in 0..self.shape.1 {
489                R::mul_assign(&mut self[(i, j)], rhs);
490            }
491        }
492    }
493}
494
495impl<R> Neg for Matrix<R>
496where
497    R: SemiRing<Additive: Invertible>,
498{
499    type Output = Self;
500
501    fn neg(self) -> Self::Output {
502        self.map(|x| R::neg(x))
503    }
504}
505
506impl<R> Neg for &Matrix<R>
507where
508    R: SemiRing<Additive: Invertible>,
509{
510    type Output = Matrix<R>;
511
512    fn neg(self) -> Self::Output {
513        self.map(|x| R::neg(x))
514    }
515}
516
517impl<R> Matrix<R>
518where
519    R: SemiRing,
520{
521    pub fn pow(self, mut n: usize) -> Self {
522        assert_eq!(self.shape.0, self.shape.1);
523        let mut res = Matrix::eye(self.shape);
524        let mut x = self;
525        while n > 0 {
526            if n & 1 == 1 {
527                res = &res * &x;
528            }
529            x = &x * &x;
530            n >>= 1;
531        }
532        res
533    }
534}
535
536impl<R> SerdeByteStr for Matrix<R>
537where
538    R: SemiRing<T: SerdeByteStr>,
539{
540    fn serialize(&self, buf: &mut Vec<u8>) {
541        self.data.serialize(buf);
542    }
543
544    fn deserialize<I>(iter: &mut I) -> Self
545    where
546        I: Iterator<Item = u8>,
547    {
548        Self::from_vec(Vec::deserialize(iter))
549    }
crates/library_checker/src/linear_algebra/system_of_linear_equations.rs (line 10)
6pub fn system_of_linear_equations(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, a: [[MInt998244353; m]; n], b: [MInt998244353; n]);
10    let a = Matrix::<AddMulOperation<MInt998244353>>::from_vec(a);
11    if let Some(sol) = a.solve_system_of_linear_equations(&b) {
12        iter_print!(writer, sol.basis.len(); @it &sol.particular);
13        for b in sol.basis {
14            iter_print!(writer, @it &b);
15        }
16    } else {
17        iter_print!(writer, -1);
18    }
19}
crates/competitive/src/algorithm/esper.rs (line 88)
81    pub fn solve(self) -> EsperSolver<R, Input, Class, FC, FF> {
82        let data: HashMap<_, _> = self
83            .data
84            .into_iter()
85            .map(|(key, SystemOfLinearEquation { a, b })| {
86                (
87                    key,
88                    Matrix::<R>::from_vec(a)
89                        .solve_system_of_linear_equations(&b)
90                        .map(|sol| sol.particular),
91                )
92            })
93            .collect();
94        EsperSolver {
95            class: self.class,
96            feature: self.feature,
97            data,
98            _marker: PhantomData,
99        }
100    }
101
102    pub fn solve_checked(self) -> EsperSolver<R, Input, Class, FC, FF>
103    where
104        Class: Debug,
105        R: Field<T: Debug, Additive: Invertible, Multiplicative: Invertible>,
106    {
107        let data: HashMap<_, _> = self
108            .data
109            .into_iter()
110            .map(|(key, SystemOfLinearEquation { a, b })| {
111                let mat = Matrix::<R>::from_vec(a);
112                let coeff = mat
113                    .solve_system_of_linear_equations(&b)
114                    .map(|sol| sol.particular);
115                if coeff.is_none() {
116                    eprintln!(
117                        "failed to solve linear equations: key={:?} A={:?} b={:?}",
118                        key, &mat.data, &b
119                    );
120                }
121                (key, coeff)
122            })
123            .collect();
124        EsperSolver {
125            class: self.class,
126            feature: self.feature,
127            data,
128            _marker: PhantomData,
129        }
130    }
Source

pub fn new_with( shape: (usize, usize), f: impl FnMut(usize, usize) -> R::T, ) -> Self

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 108)
107    pub fn transpose(&self) -> Self {
108        Self::new_with((self.shape.1, self.shape.0), |i, j| self[j][i].clone())
109    }
110
111    pub fn map<S, F>(&self, mut f: F) -> Matrix<S>
112    where
113        S: SemiRing,
114        F: FnMut(&R::T) -> S::T,
115    {
116        Matrix::<S>::new_with(self.shape, |i, j| f(&self[i][j]))
117    }
More examples
Hide additional examples
crates/competitive/src/algorithm/automata_learning.rs (lines 532-539)
523    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
524        let Some((prefix, suffix)) = self.split_sample(sample) else {
525            return false;
526        };
527        self.prefixes.push(prefix);
528        self.suffixes.push(suffix);
529        let n = self.inv_h.shape.0;
530        let prefix = &self.prefixes[n];
531        let suffix = &self.suffixes[n];
532        let u = Matrix::<F>::new_with((n, 1), |i, _| {
533            self.automaton.behavior(
534                self.prefixes[i]
535                    .iter()
536                    .cloned()
537                    .chain(suffix.iter().cloned()),
538            )
539        });
540        let v = Matrix::<F>::new_with((1, n), |_, j| {
541            self.automaton.behavior(
542                prefix
543                    .iter()
544                    .cloned()
545                    .chain(self.suffixes[j].iter().cloned()),
546            )
547        });
548        let w = Matrix::<F>::new_with((1, 1), |_, _| {
549            self.automaton
550                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
551        });
552        let t = &self.inv_h * &u;
553        let s = &v * &self.inv_h;
554        let d = F::inv(&(&w - &(&v * &t))[0][0]);
555        let dh = &t * &s;
556        for i in 0..n {
557            for j in 0..n {
558                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
559            }
560        }
561        self.inv_h
562            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
563        self.inv_h.add_row_with(|_, j| {
564            if j != n {
565                F::neg(&F::mul(&s[0][j], &d))
566            } else {
567                d.clone()
568            }
569        });
570
571        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
572            let b = &(&self.nh[x] * &t) * &s;
573            for i in 0..n {
574                for j in 0..n {
575                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
576                }
577            }
578        }
579        for (x, nh) in self.nh.iter_mut().enumerate() {
580            nh.add_col_with(|i, j| {
581                self.automaton.behavior(
582                    self.prefixes[i]
583                        .iter()
584                        .cloned()
585                        .chain([x])
586                        .chain(self.suffixes[j].iter().cloned()),
587                )
588            });
589            nh.add_row_with(|i, j| {
590                self.automaton.behavior(
591                    self.prefixes[i]
592                        .iter()
593                        .cloned()
594                        .chain([x])
595                        .chain(self.suffixes[j].iter().cloned()),
596                )
597            });
598        }
599        self.wfa
600            .initial_weights
601            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
602        self.wfa
603            .final_weights
604            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
605        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
606            transition.add_col_with(|_, _| F::zero());
607            transition.add_row_with(|_, _| F::zero());
608            for i in 0..=n {
609                for j in 0..=n {
610                    if i == n || j == n {
611                        for k in 0..=n {
612                            if i != n && j != n && k != n {
613                                continue;
614                            }
615                            F::add_assign(
616                                &mut transition[i][k],
617                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
618                            );
619                        }
620                    } else {
621                        let k = n;
622                        F::add_assign(
623                            &mut transition[i][k],
624                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
625                        );
626                    }
627                }
628            }
629        }
630        true
631    }
632    pub fn train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
633        for sample in samples {
634            self.train_sample(&sample);
635        }
636    }
637    pub fn batch_train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
638        let mut prefix_set: HashSet<_> = self.prefixes.iter().cloned().collect();
639        let mut suffix_set: HashSet<_> = self.suffixes.iter().cloned().collect();
640        for sample in samples {
641            if prefix_set.insert(sample.to_vec()) {
642                self.prefixes.push(sample.to_vec());
643            }
644            if suffix_set.insert(sample.to_vec()) {
645                self.suffixes.push(sample);
646            }
647        }
648        let mut h = Matrix::<F>::new_with((self.prefixes.len(), self.suffixes.len()), |i, j| {
649            self.automaton.behavior(
650                self.prefixes[i]
651                    .iter()
652                    .cloned()
653                    .chain(self.suffixes[j].iter().cloned()),
654            )
655        });
656        if !self.prefixes.is_empty() && !self.suffixes.is_empty() && F::is_zero(&h[0][0]) {
657            for j in 1..self.suffixes.len() {
658                if !F::is_zero(&h[0][j]) {
659                    self.suffixes.swap(0, j);
660                    for i in 0..self.prefixes.len() {
661                        h.data[i].swap(0, j);
662                    }
663                    break;
664                }
665            }
666        }
667        let mut row_id: Vec<usize> = (0..h.shape.0).collect();
668        let mut pivots = vec![];
669        h.row_reduction_with(false, |r, p, c| {
670            row_id.swap(r, p);
671            pivots.push((row_id[r], c));
672        });
673        let mut new_prefixes = vec![];
674        let mut new_suffixes = vec![];
675        for (i, j) in pivots {
676            new_prefixes.push(self.prefixes[i].clone());
677            new_suffixes.push(self.suffixes[j].clone());
678        }
679        self.prefixes = new_prefixes;
680        self.suffixes = new_suffixes;
681        assert_eq!(self.prefixes.len(), self.suffixes.len());
682        let n = self.prefixes.len();
683        let h = Matrix::<F>::new_with((n, n), |i, j| {
684            self.automaton.behavior(
685                self.prefixes[i]
686                    .iter()
687                    .cloned()
688                    .chain(self.suffixes[j].iter().cloned()),
689            )
690        });
691        self.inv_h = h.inverse().expect("Hankel matrix must be invertible");
692        self.wfa = WeightedFiniteAutomaton::<F> {
693            initial_weights: Matrix::new_with((1, n), |_, j| {
694                if self.prefixes[j].is_empty() {
695                    F::one()
696                } else {
697                    F::zero()
698                }
699            }),
700            transitions: (0..self.automaton.sigma())
701                .map(|x| {
702                    &Matrix::new_with((n, n), |i, j| {
703                        self.automaton.behavior(
704                            self.prefixes[i]
705                                .iter()
706                                .cloned()
707                                .chain([x])
708                                .chain(self.suffixes[j].iter().cloned()),
709                        )
710                    }) * &self.inv_h
711                })
712                .collect(),
713            final_weights: Matrix::new_with((n, 1), |i, _| {
714                self.automaton.behavior(self.prefixes[i].iter().cloned())
715            }),
716        };
717    }
Source

pub fn zeros(shape: (usize, usize)) -> Self

Examples found in repository?
crates/competitive/src/math/black_box_matrix.rs (line 128)
127    fn from(smat: SparseMatrix<R>) -> Self {
128        let mut mat = Matrix::zeros(smat.shape);
129        for &(i, j, ref v) in &smat.nonzero {
130            R::add_assign(&mut mat[(i, j)], v);
131        }
132        mat
133    }
More examples
Hide additional examples
crates/competitive/src/algorithm/automata_learning.rs (line 479)
473    pub fn new(automaton: A) -> Self {
474        let sigma = automaton.sigma();
475        Self {
476            automaton,
477            prefixes: vec![],
478            suffixes: vec![],
479            inv_h: Matrix::zeros((0, 0)),
480            nh: vec![Matrix::zeros((0, 0)); sigma],
481            wfa: WeightedFiniteAutomaton {
482                initial_weights: Matrix::zeros((1, 0)),
483                transitions: vec![Matrix::zeros((0, 0)); sigma],
484                final_weights: Matrix::zeros((0, 1)),
485            },
486            _marker: PhantomData,
487        }
488    }
crates/competitive/src/math/matrix.rs (line 229)
223    pub fn solve_system_of_linear_equations(
224        &self,
225        b: &[R::T],
226    ) -> Option<SystemOfLinearEquationsSolution<R>> {
227        assert_eq!(self.shape.0, b.len());
228        let (n, m) = self.shape;
229        let mut c = Matrix::<R>::zeros((n, m + 1));
230        for i in 0..n {
231            c[i][..m].clone_from_slice(&self[i]);
232            c[i][m] = b[i].clone();
233        }
234        let mut reduced = vec![!0; m + 1];
235        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
236        if reduced[m] != !0 {
237            return None;
238        }
239        let mut particular = vec![R::zero(); m];
240        let mut basis = vec![];
241        for j in 0..m {
242            if reduced[j] != !0 {
243                particular[j] = c[reduced[j]][m].clone();
244            } else {
245                let mut v = vec![R::zero(); m];
246                v[j] = R::one();
247                for i in 0..m {
248                    if reduced[i] != !0 {
249                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
250                    }
251                }
252                basis.push(v);
253            }
254        }
255        Some(SystemOfLinearEquationsSolution { particular, basis })
256    }
257
258    pub fn inverse(&self) -> Option<Matrix<R>> {
259        assert_eq!(self.shape.0, self.shape.1);
260        let n = self.shape.0;
261        let mut c = Matrix::<R>::zeros((n, n * 2));
262        for i in 0..n {
263            c[i][..n].clone_from_slice(&self[i]);
264            c[i][n + i] = R::one();
265        }
266        c.row_reduction(true);
267        if (0..n).any(|i| R::is_zero(&c[i][i])) {
268            None
269        } else {
270            Some(Self::from_vec(
271                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
272            ))
273        }
274    }
275
276    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
277        let n = self.shape.0;
278        if n == 0 {
279            return vec![R::one()];
280        }
281        assert!(self.data.iter().all(|a| a.len() == n));
282        for j in 0..(n - 1) {
283            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
284                self.data.swap(j + 1, x);
285                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
286                let inv = R::inv(&self[j + 1][j]);
287                let mut v = vec![];
288                let src = std::mem::take(&mut self[j + 1]);
289                for a in self.data[(j + 2)..].iter_mut() {
290                    let mul = R::mul(&a[j], &inv);
291                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
292                        R::sub_assign(a, &R::mul(&mul, src));
293                    }
294                    v.push(mul);
295                }
296                self[j + 1] = src;
297                for a in self.data.iter_mut() {
298                    let v = a[(j + 2)..]
299                        .iter()
300                        .zip(v.iter())
301                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
302                    R::add_assign(&mut a[j + 1], &v);
303                }
304            }
305        }
306        let mut dp = vec![vec![R::one()]];
307        for i in 0..n {
308            let mut next = vec![R::zero(); i + 2];
309            for (j, dp) in dp[i].iter().enumerate() {
310                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
311                R::add_assign(&mut next[j + 1], dp);
312            }
313            let mut mul = R::one();
314            for j in (0..i).rev() {
315                mul = R::mul(&mul, &self[j + 1][j]);
316                let c = R::mul(&mul, &self[j][i]);
317                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
318                    R::sub_assign(next, &R::mul(&c, dp));
319                }
320            }
321            dp.push(next);
322        }
323        dp.pop().unwrap()
324    }
325}
326
327impl<R> Index<usize> for Matrix<R>
328where
329    R: SemiRing,
330{
331    type Output = Vec<R::T>;
332    fn index(&self, index: usize) -> &Self::Output {
333        &self.data[index]
334    }
335}
336
337impl<R> IndexMut<usize> for Matrix<R>
338where
339    R: SemiRing,
340{
341    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
342        &mut self.data[index]
343    }
344}
345
346impl<R> Index<(usize, usize)> for Matrix<R>
347where
348    R: SemiRing,
349{
350    type Output = R::T;
351    fn index(&self, index: (usize, usize)) -> &Self::Output {
352        &self.data[index.0][index.1]
353    }
354}
355
356impl<R> IndexMut<(usize, usize)> for Matrix<R>
357where
358    R: SemiRing,
359{
360    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
361        &mut self.data[index.0][index.1]
362    }
363}
364
365macro_rules! impl_matrix_pairwise_binop {
366    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident $(where [$($clauses:tt)*])?) => {
367        impl<R> $imp_assign for Matrix<R>
368        where
369            R: SemiRing,
370            $($($clauses)*)?
371        {
372            fn $method_assign(&mut self, rhs: Self) {
373                self.pairwise_assign(&rhs, |a, b| R::$method_assign(a, b));
374            }
375        }
376        impl<R> $imp_assign<&Matrix<R>> for Matrix<R>
377        where
378            R: SemiRing,
379            $($($clauses)*)?
380        {
381            fn $method_assign(&mut self, rhs: &Self) {
382                self.pairwise_assign(rhs, |a, b| R::$method_assign(a, b));
383            }
384        }
385        impl<R> $imp for Matrix<R>
386        where
387            R: SemiRing,
388            $($($clauses)*)?
389        {
390            type Output = Matrix<R>;
391            fn $method(mut self, rhs: Self) -> Self::Output {
392                self.$method_assign(rhs);
393                self
394            }
395        }
396        impl<R> $imp<&Matrix<R>> for Matrix<R>
397        where
398            R: SemiRing,
399            $($($clauses)*)?
400        {
401            type Output = Matrix<R>;
402            fn $method(mut self, rhs: &Self) -> Self::Output {
403                self.$method_assign(rhs);
404                self
405            }
406        }
407        impl<R> $imp<Matrix<R>> for &Matrix<R>
408        where
409            R: SemiRing,
410            $($($clauses)*)?
411        {
412            type Output = Matrix<R>;
413            fn $method(self, mut rhs: Matrix<R>) -> Self::Output {
414                rhs.pairwise_assign(self, |a, b| *a = R::$method(b, a));
415                rhs
416            }
417        }
418        impl<R> $imp<&Matrix<R>> for &Matrix<R>
419        where
420            R: SemiRing,
421            $($($clauses)*)?
422        {
423            type Output = Matrix<R>;
424            fn $method(self, rhs: &Matrix<R>) -> Self::Output {
425                let mut this = self.clone();
426                this.$method_assign(rhs);
427                this
428            }
429        }
430    };
431}
432
433impl_matrix_pairwise_binop!(Add, add, AddAssign, add_assign);
434impl_matrix_pairwise_binop!(Sub, sub, SubAssign, sub_assign where [R: SemiRing<Additive: Invertible>]);
435
436impl<R> Mul for Matrix<R>
437where
438    R: SemiRing,
439{
440    type Output = Matrix<R>;
441    fn mul(self, rhs: Self) -> Self::Output {
442        (&self).mul(&rhs)
443    }
444}
445impl<R> Mul<&Matrix<R>> for Matrix<R>
446where
447    R: SemiRing,
448{
449    type Output = Matrix<R>;
450    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
451        (&self).mul(rhs)
452    }
453}
454impl<R> Mul<Matrix<R>> for &Matrix<R>
455where
456    R: SemiRing,
457{
458    type Output = Matrix<R>;
459    fn mul(self, rhs: Matrix<R>) -> Self::Output {
460        self.mul(&rhs)
461    }
462}
463impl<R> Mul<&Matrix<R>> for &Matrix<R>
464where
465    R: SemiRing,
466{
467    type Output = Matrix<R>;
468    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
469        assert_eq!(self.shape.1, rhs.shape.0);
470        let mut res = Matrix::zeros((self.shape.0, rhs.shape.1));
471        for i in 0..self.shape.0 {
472            for k in 0..self.shape.1 {
473                for j in 0..rhs.shape.1 {
474                    R::add_assign(&mut res[i][j], &R::mul(&self[i][k], &rhs[k][j]));
475                }
476            }
477        }
478        res
479    }
Source

pub fn eye(shape: (usize, usize)) -> Self

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 523)
521    pub fn pow(self, mut n: usize) -> Self {
522        assert_eq!(self.shape.0, self.shape.1);
523        let mut res = Matrix::eye(self.shape);
524        let mut x = self;
525        while n > 0 {
526            if n & 1 == 1 {
527                res = &res * &x;
528            }
529            x = &x * &x;
530            n >>= 1;
531        }
532        res
533    }
Source

pub fn transpose(&self) -> Self

Source

pub fn map<S, F>(&self, f: F) -> Matrix<S>
where S: SemiRing, F: FnMut(&R::T) -> S::T,

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 502)
501    fn neg(self) -> Self::Output {
502        self.map(|x| R::neg(x))
503    }
504}
505
506impl<R> Neg for &Matrix<R>
507where
508    R: SemiRing<Additive: Invertible>,
509{
510    type Output = Matrix<R>;
511
512    fn neg(self) -> Self::Output {
513        self.map(|x| R::neg(x))
514    }
Source

pub fn add_row_with(&mut self, f: impl FnMut(usize, usize) -> R::T)

Examples found in repository?
crates/competitive/src/algorithm/automata_learning.rs (lines 563-569)
523    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
524        let Some((prefix, suffix)) = self.split_sample(sample) else {
525            return false;
526        };
527        self.prefixes.push(prefix);
528        self.suffixes.push(suffix);
529        let n = self.inv_h.shape.0;
530        let prefix = &self.prefixes[n];
531        let suffix = &self.suffixes[n];
532        let u = Matrix::<F>::new_with((n, 1), |i, _| {
533            self.automaton.behavior(
534                self.prefixes[i]
535                    .iter()
536                    .cloned()
537                    .chain(suffix.iter().cloned()),
538            )
539        });
540        let v = Matrix::<F>::new_with((1, n), |_, j| {
541            self.automaton.behavior(
542                prefix
543                    .iter()
544                    .cloned()
545                    .chain(self.suffixes[j].iter().cloned()),
546            )
547        });
548        let w = Matrix::<F>::new_with((1, 1), |_, _| {
549            self.automaton
550                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
551        });
552        let t = &self.inv_h * &u;
553        let s = &v * &self.inv_h;
554        let d = F::inv(&(&w - &(&v * &t))[0][0]);
555        let dh = &t * &s;
556        for i in 0..n {
557            for j in 0..n {
558                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
559            }
560        }
561        self.inv_h
562            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
563        self.inv_h.add_row_with(|_, j| {
564            if j != n {
565                F::neg(&F::mul(&s[0][j], &d))
566            } else {
567                d.clone()
568            }
569        });
570
571        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
572            let b = &(&self.nh[x] * &t) * &s;
573            for i in 0..n {
574                for j in 0..n {
575                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
576                }
577            }
578        }
579        for (x, nh) in self.nh.iter_mut().enumerate() {
580            nh.add_col_with(|i, j| {
581                self.automaton.behavior(
582                    self.prefixes[i]
583                        .iter()
584                        .cloned()
585                        .chain([x])
586                        .chain(self.suffixes[j].iter().cloned()),
587                )
588            });
589            nh.add_row_with(|i, j| {
590                self.automaton.behavior(
591                    self.prefixes[i]
592                        .iter()
593                        .cloned()
594                        .chain([x])
595                        .chain(self.suffixes[j].iter().cloned()),
596                )
597            });
598        }
599        self.wfa
600            .initial_weights
601            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
602        self.wfa
603            .final_weights
604            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
605        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
606            transition.add_col_with(|_, _| F::zero());
607            transition.add_row_with(|_, _| F::zero());
608            for i in 0..=n {
609                for j in 0..=n {
610                    if i == n || j == n {
611                        for k in 0..=n {
612                            if i != n && j != n && k != n {
613                                continue;
614                            }
615                            F::add_assign(
616                                &mut transition[i][k],
617                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
618                            );
619                        }
620                    } else {
621                        let k = n;
622                        F::add_assign(
623                            &mut transition[i][k],
624                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
625                        );
626                    }
627                }
628            }
629        }
630        true
631    }
Source

pub fn add_col_with(&mut self, f: impl FnMut(usize, usize) -> R::T)

Examples found in repository?
crates/competitive/src/algorithm/automata_learning.rs (line 562)
523    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
524        let Some((prefix, suffix)) = self.split_sample(sample) else {
525            return false;
526        };
527        self.prefixes.push(prefix);
528        self.suffixes.push(suffix);
529        let n = self.inv_h.shape.0;
530        let prefix = &self.prefixes[n];
531        let suffix = &self.suffixes[n];
532        let u = Matrix::<F>::new_with((n, 1), |i, _| {
533            self.automaton.behavior(
534                self.prefixes[i]
535                    .iter()
536                    .cloned()
537                    .chain(suffix.iter().cloned()),
538            )
539        });
540        let v = Matrix::<F>::new_with((1, n), |_, j| {
541            self.automaton.behavior(
542                prefix
543                    .iter()
544                    .cloned()
545                    .chain(self.suffixes[j].iter().cloned()),
546            )
547        });
548        let w = Matrix::<F>::new_with((1, 1), |_, _| {
549            self.automaton
550                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
551        });
552        let t = &self.inv_h * &u;
553        let s = &v * &self.inv_h;
554        let d = F::inv(&(&w - &(&v * &t))[0][0]);
555        let dh = &t * &s;
556        for i in 0..n {
557            for j in 0..n {
558                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
559            }
560        }
561        self.inv_h
562            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
563        self.inv_h.add_row_with(|_, j| {
564            if j != n {
565                F::neg(&F::mul(&s[0][j], &d))
566            } else {
567                d.clone()
568            }
569        });
570
571        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
572            let b = &(&self.nh[x] * &t) * &s;
573            for i in 0..n {
574                for j in 0..n {
575                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
576                }
577            }
578        }
579        for (x, nh) in self.nh.iter_mut().enumerate() {
580            nh.add_col_with(|i, j| {
581                self.automaton.behavior(
582                    self.prefixes[i]
583                        .iter()
584                        .cloned()
585                        .chain([x])
586                        .chain(self.suffixes[j].iter().cloned()),
587                )
588            });
589            nh.add_row_with(|i, j| {
590                self.automaton.behavior(
591                    self.prefixes[i]
592                        .iter()
593                        .cloned()
594                        .chain([x])
595                        .chain(self.suffixes[j].iter().cloned()),
596                )
597            });
598        }
599        self.wfa
600            .initial_weights
601            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
602        self.wfa
603            .final_weights
604            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
605        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
606            transition.add_col_with(|_, _| F::zero());
607            transition.add_row_with(|_, _| F::zero());
608            for i in 0..=n {
609                for j in 0..=n {
610                    if i == n || j == n {
611                        for k in 0..=n {
612                            if i != n && j != n && k != n {
613                                continue;
614                            }
615                            F::add_assign(
616                                &mut transition[i][k],
617                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
618                            );
619                        }
620                    } else {
621                        let k = n;
622                        F::add_assign(
623                            &mut transition[i][k],
624                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
625                        );
626                    }
627                }
628            }
629        }
630        true
631    }
Source

pub fn pairwise_assign<F>(&mut self, other: &Self, f: F)
where F: FnMut(&mut R::T, &R::T),

Source§

impl<R> Matrix<R>
where R: Field<T: PartialEq, Additive: Invertible, Multiplicative: Invertible>,

Source

pub fn row_reduction_with<F>(&mut self, normalize: bool, f: F)
where F: FnMut(usize, usize, usize),

f: (row, pivot_row, col)

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 198)
197    pub fn row_reduction(&mut self, normalize: bool) {
198        self.row_reduction_with(normalize, |_, _, _| {});
199    }
200
201    pub fn rank(&mut self) -> usize {
202        let n = self.shape.0;
203        self.row_reduction(false);
204        (0..n)
205            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
206            .count()
207    }
208
209    pub fn determinant(&mut self) -> R::T {
210        assert_eq!(self.shape.0, self.shape.1);
211        let mut neg = false;
212        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
213        let mut d = R::one();
214        if neg {
215            d = R::neg(&d);
216        }
217        for i in 0..self.shape.0 {
218            R::mul_assign(&mut d, &self[i][i]);
219        }
220        d
221    }
222
223    pub fn solve_system_of_linear_equations(
224        &self,
225        b: &[R::T],
226    ) -> Option<SystemOfLinearEquationsSolution<R>> {
227        assert_eq!(self.shape.0, b.len());
228        let (n, m) = self.shape;
229        let mut c = Matrix::<R>::zeros((n, m + 1));
230        for i in 0..n {
231            c[i][..m].clone_from_slice(&self[i]);
232            c[i][m] = b[i].clone();
233        }
234        let mut reduced = vec![!0; m + 1];
235        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
236        if reduced[m] != !0 {
237            return None;
238        }
239        let mut particular = vec![R::zero(); m];
240        let mut basis = vec![];
241        for j in 0..m {
242            if reduced[j] != !0 {
243                particular[j] = c[reduced[j]][m].clone();
244            } else {
245                let mut v = vec![R::zero(); m];
246                v[j] = R::one();
247                for i in 0..m {
248                    if reduced[i] != !0 {
249                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
250                    }
251                }
252                basis.push(v);
253            }
254        }
255        Some(SystemOfLinearEquationsSolution { particular, basis })
256    }
More examples
Hide additional examples
crates/competitive/src/algorithm/automata_learning.rs (lines 669-672)
637    pub fn batch_train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
638        let mut prefix_set: HashSet<_> = self.prefixes.iter().cloned().collect();
639        let mut suffix_set: HashSet<_> = self.suffixes.iter().cloned().collect();
640        for sample in samples {
641            if prefix_set.insert(sample.to_vec()) {
642                self.prefixes.push(sample.to_vec());
643            }
644            if suffix_set.insert(sample.to_vec()) {
645                self.suffixes.push(sample);
646            }
647        }
648        let mut h = Matrix::<F>::new_with((self.prefixes.len(), self.suffixes.len()), |i, j| {
649            self.automaton.behavior(
650                self.prefixes[i]
651                    .iter()
652                    .cloned()
653                    .chain(self.suffixes[j].iter().cloned()),
654            )
655        });
656        if !self.prefixes.is_empty() && !self.suffixes.is_empty() && F::is_zero(&h[0][0]) {
657            for j in 1..self.suffixes.len() {
658                if !F::is_zero(&h[0][j]) {
659                    self.suffixes.swap(0, j);
660                    for i in 0..self.prefixes.len() {
661                        h.data[i].swap(0, j);
662                    }
663                    break;
664                }
665            }
666        }
667        let mut row_id: Vec<usize> = (0..h.shape.0).collect();
668        let mut pivots = vec![];
669        h.row_reduction_with(false, |r, p, c| {
670            row_id.swap(r, p);
671            pivots.push((row_id[r], c));
672        });
673        let mut new_prefixes = vec![];
674        let mut new_suffixes = vec![];
675        for (i, j) in pivots {
676            new_prefixes.push(self.prefixes[i].clone());
677            new_suffixes.push(self.suffixes[j].clone());
678        }
679        self.prefixes = new_prefixes;
680        self.suffixes = new_suffixes;
681        assert_eq!(self.prefixes.len(), self.suffixes.len());
682        let n = self.prefixes.len();
683        let h = Matrix::<F>::new_with((n, n), |i, j| {
684            self.automaton.behavior(
685                self.prefixes[i]
686                    .iter()
687                    .cloned()
688                    .chain(self.suffixes[j].iter().cloned()),
689            )
690        });
691        self.inv_h = h.inverse().expect("Hankel matrix must be invertible");
692        self.wfa = WeightedFiniteAutomaton::<F> {
693            initial_weights: Matrix::new_with((1, n), |_, j| {
694                if self.prefixes[j].is_empty() {
695                    F::one()
696                } else {
697                    F::zero()
698                }
699            }),
700            transitions: (0..self.automaton.sigma())
701                .map(|x| {
702                    &Matrix::new_with((n, n), |i, j| {
703                        self.automaton.behavior(
704                            self.prefixes[i]
705                                .iter()
706                                .cloned()
707                                .chain([x])
708                                .chain(self.suffixes[j].iter().cloned()),
709                        )
710                    }) * &self.inv_h
711                })
712                .collect(),
713            final_weights: Matrix::new_with((n, 1), |i, _| {
714                self.automaton.behavior(self.prefixes[i].iter().cloned())
715            }),
716        };
717    }
Source

pub fn row_reduction(&mut self, normalize: bool)

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 203)
201    pub fn rank(&mut self) -> usize {
202        let n = self.shape.0;
203        self.row_reduction(false);
204        (0..n)
205            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
206            .count()
207    }
208
209    pub fn determinant(&mut self) -> R::T {
210        assert_eq!(self.shape.0, self.shape.1);
211        let mut neg = false;
212        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
213        let mut d = R::one();
214        if neg {
215            d = R::neg(&d);
216        }
217        for i in 0..self.shape.0 {
218            R::mul_assign(&mut d, &self[i][i]);
219        }
220        d
221    }
222
223    pub fn solve_system_of_linear_equations(
224        &self,
225        b: &[R::T],
226    ) -> Option<SystemOfLinearEquationsSolution<R>> {
227        assert_eq!(self.shape.0, b.len());
228        let (n, m) = self.shape;
229        let mut c = Matrix::<R>::zeros((n, m + 1));
230        for i in 0..n {
231            c[i][..m].clone_from_slice(&self[i]);
232            c[i][m] = b[i].clone();
233        }
234        let mut reduced = vec![!0; m + 1];
235        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
236        if reduced[m] != !0 {
237            return None;
238        }
239        let mut particular = vec![R::zero(); m];
240        let mut basis = vec![];
241        for j in 0..m {
242            if reduced[j] != !0 {
243                particular[j] = c[reduced[j]][m].clone();
244            } else {
245                let mut v = vec![R::zero(); m];
246                v[j] = R::one();
247                for i in 0..m {
248                    if reduced[i] != !0 {
249                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
250                    }
251                }
252                basis.push(v);
253            }
254        }
255        Some(SystemOfLinearEquationsSolution { particular, basis })
256    }
257
258    pub fn inverse(&self) -> Option<Matrix<R>> {
259        assert_eq!(self.shape.0, self.shape.1);
260        let n = self.shape.0;
261        let mut c = Matrix::<R>::zeros((n, n * 2));
262        for i in 0..n {
263            c[i][..n].clone_from_slice(&self[i]);
264            c[i][n + i] = R::one();
265        }
266        c.row_reduction(true);
267        if (0..n).any(|i| R::is_zero(&c[i][i])) {
268            None
269        } else {
270            Some(Self::from_vec(
271                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
272            ))
273        }
274    }
Source

pub fn rank(&mut self) -> usize

Source

pub fn determinant(&mut self) -> R::T

Source

pub fn solve_system_of_linear_equations( &self, b: &[R::T], ) -> Option<SystemOfLinearEquationsSolution<R>>

Examples found in repository?
crates/library_checker/src/linear_algebra/system_of_linear_equations.rs (line 11)
6pub fn system_of_linear_equations(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, a: [[MInt998244353; m]; n], b: [MInt998244353; n]);
10    let a = Matrix::<AddMulOperation<MInt998244353>>::from_vec(a);
11    if let Some(sol) = a.solve_system_of_linear_equations(&b) {
12        iter_print!(writer, sol.basis.len(); @it &sol.particular);
13        for b in sol.basis {
14            iter_print!(writer, @it &b);
15        }
16    } else {
17        iter_print!(writer, -1);
18    }
19}
More examples
Hide additional examples
crates/competitive/src/algorithm/esper.rs (line 89)
81    pub fn solve(self) -> EsperSolver<R, Input, Class, FC, FF> {
82        let data: HashMap<_, _> = self
83            .data
84            .into_iter()
85            .map(|(key, SystemOfLinearEquation { a, b })| {
86                (
87                    key,
88                    Matrix::<R>::from_vec(a)
89                        .solve_system_of_linear_equations(&b)
90                        .map(|sol| sol.particular),
91                )
92            })
93            .collect();
94        EsperSolver {
95            class: self.class,
96            feature: self.feature,
97            data,
98            _marker: PhantomData,
99        }
100    }
101
102    pub fn solve_checked(self) -> EsperSolver<R, Input, Class, FC, FF>
103    where
104        Class: Debug,
105        R: Field<T: Debug, Additive: Invertible, Multiplicative: Invertible>,
106    {
107        let data: HashMap<_, _> = self
108            .data
109            .into_iter()
110            .map(|(key, SystemOfLinearEquation { a, b })| {
111                let mat = Matrix::<R>::from_vec(a);
112                let coeff = mat
113                    .solve_system_of_linear_equations(&b)
114                    .map(|sol| sol.particular);
115                if coeff.is_none() {
116                    eprintln!(
117                        "failed to solve linear equations: key={:?} A={:?} b={:?}",
118                        key, &mat.data, &b
119                    );
120                }
121                (key, coeff)
122            })
123            .collect();
124        EsperSolver {
125            class: self.class,
126            feature: self.feature,
127            data,
128            _marker: PhantomData,
129        }
130    }
Source

pub fn inverse(&self) -> Option<Matrix<R>>

Examples found in repository?
crates/competitive/src/algorithm/automata_learning.rs (line 691)
637    pub fn batch_train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
638        let mut prefix_set: HashSet<_> = self.prefixes.iter().cloned().collect();
639        let mut suffix_set: HashSet<_> = self.suffixes.iter().cloned().collect();
640        for sample in samples {
641            if prefix_set.insert(sample.to_vec()) {
642                self.prefixes.push(sample.to_vec());
643            }
644            if suffix_set.insert(sample.to_vec()) {
645                self.suffixes.push(sample);
646            }
647        }
648        let mut h = Matrix::<F>::new_with((self.prefixes.len(), self.suffixes.len()), |i, j| {
649            self.automaton.behavior(
650                self.prefixes[i]
651                    .iter()
652                    .cloned()
653                    .chain(self.suffixes[j].iter().cloned()),
654            )
655        });
656        if !self.prefixes.is_empty() && !self.suffixes.is_empty() && F::is_zero(&h[0][0]) {
657            for j in 1..self.suffixes.len() {
658                if !F::is_zero(&h[0][j]) {
659                    self.suffixes.swap(0, j);
660                    for i in 0..self.prefixes.len() {
661                        h.data[i].swap(0, j);
662                    }
663                    break;
664                }
665            }
666        }
667        let mut row_id: Vec<usize> = (0..h.shape.0).collect();
668        let mut pivots = vec![];
669        h.row_reduction_with(false, |r, p, c| {
670            row_id.swap(r, p);
671            pivots.push((row_id[r], c));
672        });
673        let mut new_prefixes = vec![];
674        let mut new_suffixes = vec![];
675        for (i, j) in pivots {
676            new_prefixes.push(self.prefixes[i].clone());
677            new_suffixes.push(self.suffixes[j].clone());
678        }
679        self.prefixes = new_prefixes;
680        self.suffixes = new_suffixes;
681        assert_eq!(self.prefixes.len(), self.suffixes.len());
682        let n = self.prefixes.len();
683        let h = Matrix::<F>::new_with((n, n), |i, j| {
684            self.automaton.behavior(
685                self.prefixes[i]
686                    .iter()
687                    .cloned()
688                    .chain(self.suffixes[j].iter().cloned()),
689            )
690        });
691        self.inv_h = h.inverse().expect("Hankel matrix must be invertible");
692        self.wfa = WeightedFiniteAutomaton::<F> {
693            initial_weights: Matrix::new_with((1, n), |_, j| {
694                if self.prefixes[j].is_empty() {
695                    F::one()
696                } else {
697                    F::zero()
698                }
699            }),
700            transitions: (0..self.automaton.sigma())
701                .map(|x| {
702                    &Matrix::new_with((n, n), |i, j| {
703                        self.automaton.behavior(
704                            self.prefixes[i]
705                                .iter()
706                                .cloned()
707                                .chain([x])
708                                .chain(self.suffixes[j].iter().cloned()),
709                        )
710                    }) * &self.inv_h
711                })
712                .collect(),
713            final_weights: Matrix::new_with((n, 1), |i, _| {
714                self.automaton.behavior(self.prefixes[i].iter().cloned())
715            }),
716        };
717    }
Source

pub fn characteristic_polynomial(&mut self) -> Vec<R::T>

Examples found in repository?
crates/library_checker/src/linear_algebra/characteristic_polynomial.rs (line 10)
6pub fn characteristic_polynomial(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [[MInt998244353; n]; n]);
10    let p = Matrix::<AddMulOperation<_>>::from_vec(a).characteristic_polynomial();
11    iter_print!(writer, @it p);
12}
More examples
Hide additional examples
crates/competitive/src/math/mint_matrix.rs (line 81)
41    fn determinant_linear_non_singular(mut self, mut other: Self) -> Option<Vec<MInt<M>>>
42    where
43        M: MIntBase,
44    {
45        let n = self.data.len();
46        let mut f = MInt::one();
47        for d in 0..n {
48            let i = other.data.iter().position(|other| !other[d].is_zero())?;
49            if i != d {
50                self.data.swap(i, d);
51                other.data.swap(i, d);
52                f = -f;
53            }
54            f *= other[d][d];
55            let r = other[d][d].inv();
56            for j in 0..n {
57                self[d][j] *= r;
58                other[d][j] *= r;
59            }
60            assert!(other[d][d].is_one());
61            for i in d + 1..n {
62                let a = other[i][d];
63                for k in 0..n {
64                    self[i][k] = self[i][k] - a * self[d][k];
65                    other[i][k] = other[i][k] - a * other[d][k];
66                }
67            }
68            for j in d + 1..n {
69                let a = other[d][j];
70                for k in 0..n {
71                    self[k][j] = self[k][j] - a * self[k][d];
72                    other[k][j] = other[k][j] - a * other[k][d];
73                }
74            }
75        }
76        for s in self.data.iter_mut() {
77            for s in s.iter_mut() {
78                *s = -*s;
79            }
80        }
81        let mut p = self.characteristic_polynomial();
82        for p in p.iter_mut() {
83            *p *= f;
84        }
85        Some(p)
86    }
Source§

impl<R> Matrix<R>
where R: SemiRing,

Source

pub fn pow(self, n: usize) -> Self

Source§

impl<M> Matrix<AddMulOperation<MInt<M>>>
where M: MIntBase,

Source

fn determinant_linear_non_singular(self, other: Self) -> Option<Vec<MInt<M>>>
where M: MIntBase,

Examples found in repository?
crates/competitive/src/math/mint_matrix.rs (line 31)
19    fn determinant_linear(mut self, other: Self) -> Option<Vec<MInt<M>>>
20    where
21        M: MIntConvert<usize> + MIntConvert<u64>,
22    {
23        let mut rng = Xorshift::new();
24        let a = MInt::from(rng.rand64());
25        let n = self.data.len();
26        for i in 0..n {
27            for j in 0..n {
28                self[i][j] += other[i][j] * a;
29            }
30        }
31        let mut f = other.determinant_linear_non_singular(self)?;
32        f.reverse();
33        Some(taylor_shift::<M>(f, -a))
34    }

Trait Implementations§

Source§

impl<R> Add<&Matrix<R>> for &Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: &Matrix<R>) -> Self::Output

Performs the + operation. Read more
Source§

impl<R> Add<&Matrix<R>> for Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: &Self) -> Self::Output

Performs the + operation. Read more
Source§

impl<R> Add<Matrix<R>> for &Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: Matrix<R>) -> Self::Output

Performs the + operation. Read more
Source§

impl<R> Add for Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: Self) -> Self::Output

Performs the + operation. Read more
Source§

impl<R> AddAssign<&Matrix<R>> for Matrix<R>
where R: SemiRing,

Source§

fn add_assign(&mut self, rhs: &Self)

Performs the += operation. Read more
Source§

impl<R> AddAssign for Matrix<R>
where R: SemiRing,

Source§

fn add_assign(&mut self, rhs: Self)

Performs the += operation. Read more
Source§

impl<R> BlackBoxMatrix<R> for Matrix<R>
where R: SemiRing,

Source§

fn apply(&self, v: &[R::T]) -> Vec<R::T>

Source§

fn shape(&self) -> (usize, usize)

Source§

impl<R> Clone for Matrix<R>
where R: SemiRing,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<R> Debug for Matrix<R>
where R: SemiRing<T: Debug>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<R> From<Matrix<R>> for SparseMatrix<R>
where R: SemiRing<T: PartialEq>,

Source§

fn from(mat: Matrix<R>) -> Self

Converts to this type from the input type.
Source§

impl<R> From<SparseMatrix<R>> for Matrix<R>
where R: SemiRing,

Source§

fn from(smat: SparseMatrix<R>) -> Self

Converts to this type from the input type.
Source§

impl<R> Index<(usize, usize)> for Matrix<R>
where R: SemiRing,

Source§

type Output = <R as SemiRing>::T

The returned type after indexing.
Source§

fn index(&self, index: (usize, usize)) -> &Self::Output

Performs the indexing (container[index]) operation. Read more
Source§

impl<R> Index<usize> for Matrix<R>
where R: SemiRing,

Source§

type Output = Vec<<R as SemiRing>::T>

The returned type after indexing.
Source§

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation. Read more
Source§

impl<R> IndexMut<(usize, usize)> for Matrix<R>
where R: SemiRing,

Source§

fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation. Read more
Source§

impl<R> IndexMut<usize> for Matrix<R>
where R: SemiRing,

Source§

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation. Read more
Source§

impl<M> MIntMatrix<M> for Matrix<AddMulOperation<MInt<M>>>
where M: MIntBase,

Source§

fn determinant_linear(self, other: Self) -> Option<Vec<MInt<M>>>
where M: MIntConvert<usize> + MIntConvert<u64>,

det(self + other * x)
Source§

impl<R> Mul<&Matrix<R>> for &Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the * operator.
Source§

fn mul(self, rhs: &Matrix<R>) -> Self::Output

Performs the * operation. Read more
Source§

impl<R> Mul<&Matrix<R>> for Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the * operator.
Source§

fn mul(self, rhs: &Matrix<R>) -> Self::Output

Performs the * operation. Read more
Source§

impl<R> Mul<Matrix<R>> for &Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the * operator.
Source§

fn mul(self, rhs: Matrix<R>) -> Self::Output

Performs the * operation. Read more
Source§

impl<R> Mul for Matrix<R>
where R: SemiRing,

Source§

type Output = Matrix<R>

The resulting type after applying the * operator.
Source§

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation. Read more
Source§

impl<R> MulAssign<&<R as SemiRing>::T> for Matrix<R>
where R: SemiRing,

Source§

fn mul_assign(&mut self, rhs: &R::T)

Performs the *= operation. Read more
Source§

impl<R> Neg for &Matrix<R>
where R: SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn neg(self) -> Self::Output

Performs the unary - operation. Read more
Source§

impl<R> Neg for Matrix<R>
where R: SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn neg(self) -> Self::Output

Performs the unary - operation. Read more
Source§

impl<R> PartialEq for Matrix<R>
where R: SemiRing<T: PartialEq>,

Source§

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<R> SerdeByteStr for Matrix<R>
where R: SemiRing<T: SerdeByteStr>,

Source§

fn serialize(&self, buf: &mut Vec<u8>)

Source§

fn deserialize<I>(iter: &mut I) -> Self
where I: Iterator<Item = u8>,

Source§

fn serialize_bytestr(&self) -> String

Source§

fn deserialize_from_bytes(bytes: &[u8]) -> Self
where Self: Sized,

Source§

impl<R> Sub<&Matrix<R>> for &Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: &Matrix<R>) -> Self::Output

Performs the - operation. Read more
Source§

impl<R> Sub<&Matrix<R>> for Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: &Self) -> Self::Output

Performs the - operation. Read more
Source§

impl<R> Sub<Matrix<R>> for &Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: Matrix<R>) -> Self::Output

Performs the - operation. Read more
Source§

impl<R> Sub for Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

type Output = Matrix<R>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation. Read more
Source§

impl<R> SubAssign<&Matrix<R>> for Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

fn sub_assign(&mut self, rhs: &Self)

Performs the -= operation. Read more
Source§

impl<R> SubAssign for Matrix<R>
where R: SemiRing + SemiRing<Additive: Invertible>,

Source§

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation. Read more
Source§

impl<R> Eq for Matrix<R>
where R: SemiRing<T: Eq>,

Auto Trait Implementations§

§

impl<R> Freeze for Matrix<R>

§

impl<R> RefUnwindSafe for Matrix<R>
where <R as SemiRing>::T: RefUnwindSafe,

§

impl<R> Send for Matrix<R>
where <R as SemiRing>::T: Send,

§

impl<R> Sync for Matrix<R>
where <R as SemiRing>::T: Sync,

§

impl<R> Unpin for Matrix<R>
where <R as SemiRing>::T: Unpin,

§

impl<R> UnwindSafe for Matrix<R>
where <R as SemiRing>::T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<M, B> BlackBoxMIntMatrix<M> for B
where M: MIntBase, B: BlackBoxMatrix<AddMulOperation<MInt<M>>>,

Source§

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

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>,

Source§

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

Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.