Trait SemiRing

Source

pub trait SemiRing {
    type T: Clone;
    type Additive: AbelianMonoid<T = Self::T>;
    type Multiplicative: Monoid<T = Self::T>;

    // Provided methods
    fn zero() -> Self::T { ... }
    fn is_zero(x: &Self::T) -> bool
       where Self::T: PartialEq { ... }
    fn one() -> Self::T { ... }
    fn is_one(x: &Self::T) -> bool
       where Self::T: PartialEq { ... }
    fn add(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn mul(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn add_assign(x: &mut Self::T, y: &Self::T) { ... }
    fn mul_assign(x: &mut Self::T, y: &Self::T) { ... }
}

Required Associated Types§

Source

type T: Clone

Source

type Additive: AbelianMonoid<T = Self::T>

Source

type Multiplicative: Monoid<T = Self::T>

Provided Methods§

Source

fn zero() -> Self::T

additive identity: $0$

Examples found in repository ?

crates/competitive/src/graph/shortest_path.rs (line 93)

92    fn inf() -> Self::T {
93        PartialIgnoredOrd(M::T::maximum(), S::zero())
94    }

More examples

Hide additional examples

crates/competitive/src/algebra/ring.rs (line 20)

16    fn is_zero(x: &Self::T) -> bool
17    where
18        Self::T: PartialEq,
19    {
20        *x == Self::zero()
21    }

crates/competitive/src/math/matrix.rs (line 97)

94    pub fn zeros(shape: (usize, usize)) -> Self {
95        Self {
96            shape,
97            data: vec![vec![R::zero(); shape.1]; shape.0],
98            _marker: PhantomData,
99        }
100    }
101
102    pub fn eye(shape: (usize, usize)) -> Self {
103        let mut data = vec![vec![R::zero(); shape.1]; shape.0];
104        for (i, d) in data.iter_mut().enumerate().take(shape.1) {
105            d[i] = R::one();
106        }
107        Self {
108            shape,
109            data,
110            _marker: PhantomData,
111        }
112    }
113
114    pub fn transpose(&self) -> Self {
115        Self::new_with((self.shape.1, self.shape.0), |i, j| self[j][i].clone())
116    }
117
118    pub fn map<S, F>(&self, mut f: F) -> Matrix<S>
119    where
120        S: SemiRing,
121        F: FnMut(&R::T) -> S::T,
122    {
123        Matrix::<S>::new_with(self.shape, |i, j| f(&self[i][j]))
124    }
125
126    pub fn add_row_with(&mut self, mut f: impl FnMut(usize, usize) -> R::T) {
127        self.data
128            .push((0..self.shape.1).map(|j| f(self.shape.0, j)).collect());
129        self.shape.0 += 1;
130    }
131
132    pub fn add_col_with(&mut self, mut f: impl FnMut(usize, usize) -> R::T) {
133        for i in 0..self.shape.0 {
134            self.data[i].push(f(i, self.shape.1));
135        }
136        self.shape.1 += 1;
137    }
138
139    pub fn pairwise_assign<F>(&mut self, other: &Self, mut f: F)
140    where
141        F: FnMut(&mut R::T, &R::T),
142    {
143        assert_eq!(self.shape, other.shape);
144        for i in 0..self.shape.0 {
145            for j in 0..self.shape.1 {
146                f(&mut self[i][j], &other[i][j]);
147            }
148        }
149    }
150}
151
152#[derive(Debug)]
153pub struct SystemOfLinearEquationsSolution<R>
154where
155    R: Field,
156    R::Additive: Invertible,
157    R::Multiplicative: Invertible,
158{
159    pub particular: Vec<R::T>,
160    pub basis: Vec<Vec<R::T>>,
161}
162
163impl<R> Matrix<R>
164where
165    R: Field,
166    R::Additive: Invertible,
167    R::Multiplicative: Invertible,
168    R::T: PartialEq,
169{
170    /// f: (row, pivot_row, col)
171    pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
172    where
173        F: FnMut(usize, usize, usize),
174    {
175        let (n, m) = self.shape;
176        let mut c = 0;
177        for r in 0..n {
178            loop {
179                if c >= m {
180                    return;
181                }
182                if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
183                    f(r, pivot, c);
184                    self.data.swap(r, pivot);
185                    break;
186                };
187                c += 1;
188            }
189            let d = R::inv(&self[r][c]);
190            if normalize {
191                for j in c..m {
192                    R::mul_assign(&mut self[r][j], &d);
193                }
194            }
195            for i in (0..n).filter(|&i| i != r) {
196                let mut e = self[i][c].clone();
197                if !normalize {
198                    R::mul_assign(&mut e, &d);
199                }
200                for j in c..m {
201                    let e = R::mul(&e, &self[r][j]);
202                    R::sub_assign(&mut self[i][j], &e);
203                }
204            }
205            c += 1;
206        }
207    }
208
209    pub fn row_reduction(&mut self, normalize: bool) {
210        self.row_reduction_with(normalize, |_, _, _| {});
211    }
212
213    pub fn rank(&mut self) -> usize {
214        let n = self.shape.0;
215        self.row_reduction(false);
216        (0..n)
217            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
218            .count()
219    }
220
221    pub fn determinant(&mut self) -> R::T {
222        assert_eq!(self.shape.0, self.shape.1);
223        let mut neg = false;
224        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
225        let mut d = R::one();
226        if neg {
227            d = R::neg(&d);
228        }
229        for i in 0..self.shape.0 {
230            R::mul_assign(&mut d, &self[i][i]);
231        }
232        d
233    }
234
235    pub fn solve_system_of_linear_equations(
236        &self,
237        b: &[R::T],
238    ) -> Option<SystemOfLinearEquationsSolution<R>> {
239        assert_eq!(self.shape.0, b.len());
240        let (n, m) = self.shape;
241        let mut c = Matrix::<R>::zeros((n, m + 1));
242        for i in 0..n {
243            c[i][..m].clone_from_slice(&self[i]);
244            c[i][m] = b[i].clone();
245        }
246        let mut reduced = vec![!0; m + 1];
247        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
248        if reduced[m] != !0 {
249            return None;
250        }
251        let mut particular = vec![R::zero(); m];
252        let mut basis = vec![];
253        for j in 0..m {
254            if reduced[j] != !0 {
255                particular[j] = c[reduced[j]][m].clone();
256            } else {
257                let mut v = vec![R::zero(); m];
258                v[j] = R::one();
259                for i in 0..m {
260                    if reduced[i] != !0 {
261                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
262                    }
263                }
264                basis.push(v);
265            }
266        }
267        Some(SystemOfLinearEquationsSolution { particular, basis })
268    }
269
270    pub fn inverse(&self) -> Option<Matrix<R>> {
271        assert_eq!(self.shape.0, self.shape.1);
272        let n = self.shape.0;
273        let mut c = Matrix::<R>::zeros((n, n * 2));
274        for i in 0..n {
275            c[i][..n].clone_from_slice(&self[i]);
276            c[i][n + i] = R::one();
277        }
278        c.row_reduction(true);
279        if (0..n).any(|i| R::is_zero(&c[i][i])) {
280            None
281        } else {
282            Some(Self::from_vec(
283                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
284            ))
285        }
286    }
287
288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }

crates/competitive/src/math/floor_sum.rs (line 125)

124    fn to_x() -> FloorSumData<R, X, Y> {
125        let mut dp = array![array![R::zero(); Y]; X];
126        dp[0][0] = R::one();
127        FloorSumData {
128            dp,
129            dx: R::one(),
130            dy: R::zero(),
131            _marker: PhantomData,
132        }
133    }
134    fn to_y() -> FloorSumData<R, X, Y> {
135        FloorSumData {
136            dp: array![array![R::zero(); Y]; X],
137            dx: R::zero(),
138            dy: R::one(),
139            _marker: PhantomData,
140        }
141    }
142}
143
144impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>
145where
146    R: Ring,
147    R::Additive: Invertible,
148{
149    fn offset(x: i64, y: i64) -> FloorSumData<R, X, Y> {
150        FloorSumData {
151            dp: array![array![R::zero(); Y]; X],
152            dx: R::Additive::signed_pow(R::one(), x),
153            dy: R::Additive::signed_pow(R::one(), y),
154            _marker: PhantomData,
155        }
156    }
157}
158
159impl<R, const X: usize, const Y: usize> Magma for FloorSum<R, X, Y>
160where
161    R: SemiRing,
162{
163    type T = FloorSumData<R, X, Y>;
164
165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }
224}
225
226impl<R, const X: usize, const Y: usize> Unital for FloorSum<R, X, Y>
227where
228    R: SemiRing,
229{
230    fn unit() -> Self::T {
231        FloorSumData {
232            dp: array![array![R::zero(); Y]; X],
233            dx: R::zero(),
234            dy: R::zero(),
235            _marker: PhantomData,
236        }
237    }

crates/competitive/src/math/black_box_matrix.rs (line 25)

23    fn apply(&self, v: &[R::T]) -> Vec<R::T> {
24        assert_eq!(self.shape.1, v.len());
25        let mut res = vec![R::zero(); self.shape.0];
26        for i in 0..self.shape.0 {
27            for j in 0..self.shape.1 {
28                R::add_assign(&mut res[i], &R::mul(&self[(i, j)], &v[j]));
29            }
30        }
31        res
32    }
33
34    fn shape(&self) -> (usize, usize) {
35        self.shape
36    }
37}
38
39pub struct SparseMatrix<R>
40where
41    R: SemiRing,
42{
43    shape: (usize, usize),
44    nonzero: Vec<(usize, usize, R::T)>,
45}
46
47impl<R> Debug for SparseMatrix<R>
48where
49    R: SemiRing,
50    R::T: Debug,
51{
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        f.debug_struct("SparseMatrix")
54            .field("shape", &self.shape)
55            .field("nonzero", &self.nonzero)
56            .finish()
57    }
58}
59
60impl<R> Clone for SparseMatrix<R>
61where
62    R: SemiRing,
63{
64    fn clone(&self) -> Self {
65        Self {
66            shape: self.shape,
67            nonzero: self.nonzero.clone(),
68        }
69    }
70}
71
72impl<R> SparseMatrix<R>
73where
74    R: SemiRing,
75{
76    pub fn new(shape: (usize, usize)) -> Self {
77        Self {
78            shape,
79            nonzero: vec![],
80        }
81    }
82    pub fn new_with<F>(shape: (usize, usize), f: F) -> Self
83    where
84        R::T: PartialEq,
85        F: Fn(usize, usize) -> R::T,
86    {
87        let mut nonzero = vec![];
88        for i in 0..shape.0 {
89            for j in 0..shape.1 {
90                let v = f(i, j);
91                if !R::is_zero(&v) {
92                    nonzero.push((i, j, v));
93                }
94            }
95        }
96        Self { shape, nonzero }
97    }
98    pub fn from_nonzero(shape: (usize, usize), nonzero: Vec<(usize, usize, R::T)>) -> Self {
99        Self { shape, nonzero }
100    }
101}
102
103impl<R> From<Matrix<R>> for SparseMatrix<R>
104where
105    R: SemiRing,
106    R::T: PartialEq,
107{
108    fn from(mat: Matrix<R>) -> Self {
109        let mut nonzero = vec![];
110        for i in 0..mat.shape.0 {
111            for j in 0..mat.shape.1 {
112                let v = mat[(i, j)].clone();
113                if !R::is_zero(&v) {
114                    nonzero.push((i, j, v));
115                }
116            }
117        }
118        Self {
119            shape: mat.shape,
120            nonzero,
121        }
122    }
123}
124
125impl<R> From<SparseMatrix<R>> for Matrix<R>
126where
127    R: SemiRing,
128{
129    fn from(smat: SparseMatrix<R>) -> Self {
130        let mut mat = Matrix::zeros(smat.shape);
131        for &(i, j, ref v) in &smat.nonzero {
132            R::add_assign(&mut mat[(i, j)], v);
133        }
134        mat
135    }
136}
137
138impl<R> BlackBoxMatrix<R> for SparseMatrix<R>
139where
140    R: SemiRing,
141{
142    fn apply(&self, v: &[R::T]) -> Vec<R::T> {
143        assert_eq!(self.shape.1, v.len());
144        let mut res = vec![R::zero(); self.shape.0];
145        for &(i, j, ref val) in &self.nonzero {
146            R::add_assign(&mut res[i], &R::mul(val, &v[j]));
147        }
148        res
149    }

crates/competitive/src/math/subset_convolve.rs (line 23)

21    fn transform(t: Self::T, len: usize) -> Self::F {
22        let k = len.trailing_zeros() as usize;
23        let mut f = vec![vec![R::zero(); len]; k + 1];
24        for (i, t) in t.iter().enumerate() {
25            let f = &mut f[i.count_ones() as usize][i];
26            *f = R::add(f, t);
27        }
28        for f in f.iter_mut() {
29            BitwiseorConvolve::<R::Additive>::zeta_transform(f);
30        }
31        f
32    }
33
34    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
35        for f in f.iter_mut() {
36            BitwiseorConvolve::<R::Additive>::mobius_transform(f);
37        }
38        let mut t = vec![R::zero(); len];
39        for (i, t) in t.iter_mut().enumerate() {
40            *t = R::add(t, &f[i.count_ones() as usize][i]);
41        }
42        t
43    }

Additional examples can be found in:

Source

fn is_zero(x: &Self::T) -> bool
where Self::T: PartialEq,

checks if the element is zero

Examples found in repository ?

crates/competitive/src/math/black_box_matrix.rs (line 91)

82    pub fn new_with<F>(shape: (usize, usize), f: F) -> Self
83    where
84        R::T: PartialEq,
85        F: Fn(usize, usize) -> R::T,
86    {
87        let mut nonzero = vec![];
88        for i in 0..shape.0 {
89            for j in 0..shape.1 {
90                let v = f(i, j);
91                if !R::is_zero(&v) {
92                    nonzero.push((i, j, v));
93                }
94            }
95        }
96        Self { shape, nonzero }
97    }
98    pub fn from_nonzero(shape: (usize, usize), nonzero: Vec<(usize, usize, R::T)>) -> Self {
99        Self { shape, nonzero }
100    }
101}
102
103impl<R> From<Matrix<R>> for SparseMatrix<R>
104where
105    R: SemiRing,
106    R::T: PartialEq,
107{
108    fn from(mat: Matrix<R>) -> Self {
109        let mut nonzero = vec![];
110        for i in 0..mat.shape.0 {
111            for j in 0..mat.shape.1 {
112                let v = mat[(i, j)].clone();
113                if !R::is_zero(&v) {
114                    nonzero.push((i, j, v));
115                }
116            }
117        }
118        Self {
119            shape: mat.shape,
120            nonzero,
121        }
122    }

More examples

Hide additional examples

crates/competitive/src/math/matrix.rs (line 182)

171    pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
172    where
173        F: FnMut(usize, usize, usize),
174    {
175        let (n, m) = self.shape;
176        let mut c = 0;
177        for r in 0..n {
178            loop {
179                if c >= m {
180                    return;
181                }
182                if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
183                    f(r, pivot, c);
184                    self.data.swap(r, pivot);
185                    break;
186                };
187                c += 1;
188            }
189            let d = R::inv(&self[r][c]);
190            if normalize {
191                for j in c..m {
192                    R::mul_assign(&mut self[r][j], &d);
193                }
194            }
195            for i in (0..n).filter(|&i| i != r) {
196                let mut e = self[i][c].clone();
197                if !normalize {
198                    R::mul_assign(&mut e, &d);
199                }
200                for j in c..m {
201                    let e = R::mul(&e, &self[r][j]);
202                    R::sub_assign(&mut self[i][j], &e);
203                }
204            }
205            c += 1;
206        }
207    }
208
209    pub fn row_reduction(&mut self, normalize: bool) {
210        self.row_reduction_with(normalize, |_, _, _| {});
211    }
212
213    pub fn rank(&mut self) -> usize {
214        let n = self.shape.0;
215        self.row_reduction(false);
216        (0..n)
217            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
218            .count()
219    }
220
221    pub fn determinant(&mut self) -> R::T {
222        assert_eq!(self.shape.0, self.shape.1);
223        let mut neg = false;
224        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
225        let mut d = R::one();
226        if neg {
227            d = R::neg(&d);
228        }
229        for i in 0..self.shape.0 {
230            R::mul_assign(&mut d, &self[i][i]);
231        }
232        d
233    }
234
235    pub fn solve_system_of_linear_equations(
236        &self,
237        b: &[R::T],
238    ) -> Option<SystemOfLinearEquationsSolution<R>> {
239        assert_eq!(self.shape.0, b.len());
240        let (n, m) = self.shape;
241        let mut c = Matrix::<R>::zeros((n, m + 1));
242        for i in 0..n {
243            c[i][..m].clone_from_slice(&self[i]);
244            c[i][m] = b[i].clone();
245        }
246        let mut reduced = vec![!0; m + 1];
247        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
248        if reduced[m] != !0 {
249            return None;
250        }
251        let mut particular = vec![R::zero(); m];
252        let mut basis = vec![];
253        for j in 0..m {
254            if reduced[j] != !0 {
255                particular[j] = c[reduced[j]][m].clone();
256            } else {
257                let mut v = vec![R::zero(); m];
258                v[j] = R::one();
259                for i in 0..m {
260                    if reduced[i] != !0 {
261                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
262                    }
263                }
264                basis.push(v);
265            }
266        }
267        Some(SystemOfLinearEquationsSolution { particular, basis })
268    }
269
270    pub fn inverse(&self) -> Option<Matrix<R>> {
271        assert_eq!(self.shape.0, self.shape.1);
272        let n = self.shape.0;
273        let mut c = Matrix::<R>::zeros((n, n * 2));
274        for i in 0..n {
275            c[i][..n].clone_from_slice(&self[i]);
276            c[i][n + i] = R::one();
277        }
278        c.row_reduction(true);
279        if (0..n).any(|i| R::is_zero(&c[i][i])) {
280            None
281        } else {
282            Some(Self::from_vec(
283                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
284            ))
285        }
286    }
287
288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }

crates/competitive/src/algorithm/automata_learning.rs (line 515)

514    fn split_sample(&mut self, sample: &[usize]) -> Option<(Vec<usize>, Vec<usize>)> {
515        if self.prefixes.is_empty() && !F::is_zero(&self.automaton.behavior(sample.iter().cloned()))
516        {
517            return Some((vec![], sample.to_vec()));
518        }
519        let expected = self.automaton.behavior(sample.iter().cloned());
520        if expected == self.wfa.behavior(sample.iter().cloned()) {
521            return None;
522        }
523        let n = sample.len();
524        let dim = self.wfa.final_weights.shape.0;
525        let mut states: Vec<(Matrix<F>, usize)> = Vec::with_capacity(n + 1);
526        let mut v = self.wfa.final_weights.clone();
527        states.push((v.clone(), n));
528        for k in (0..n).rev() {
529            v = &self.wfa.transitions[sample[k]] * &v;
530            states.push((v.clone(), k));
531        }
532        states.reverse();
533        let split = states.partition_point(|(state, k)| {
534            (0..dim).any(|j| {
535                self.automaton.behavior(
536                    self.prefixes[j]
537                        .iter()
538                        .cloned()
539                        .chain(sample[*k..].iter().cloned()),
540                ) != state[j][0]
541            })
542        });
543        Some((sample[..split].to_vec(), sample[split..].to_vec()))
544    }
545    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
546        let Some((prefix, suffix)) = self.split_sample(sample) else {
547            return false;
548        };
549        self.prefixes.push(prefix);
550        self.suffixes.push(suffix);
551        let n = self.inv_h.shape.0;
552        let prefix = &self.prefixes[n];
553        let suffix = &self.suffixes[n];
554        let u = Matrix::<F>::new_with((n, 1), |i, _| {
555            self.automaton.behavior(
556                self.prefixes[i]
557                    .iter()
558                    .cloned()
559                    .chain(suffix.iter().cloned()),
560            )
561        });
562        let v = Matrix::<F>::new_with((1, n), |_, j| {
563            self.automaton.behavior(
564                prefix
565                    .iter()
566                    .cloned()
567                    .chain(self.suffixes[j].iter().cloned()),
568            )
569        });
570        let w = Matrix::<F>::new_with((1, 1), |_, _| {
571            self.automaton
572                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
573        });
574        let t = &self.inv_h * &u;
575        let s = &v * &self.inv_h;
576        let d = F::inv(&(&w - &(&v * &t))[0][0]);
577        let dh = &t * &s;
578        for i in 0..n {
579            for j in 0..n {
580                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
581            }
582        }
583        self.inv_h
584            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
585        self.inv_h.add_row_with(|_, j| {
586            if j != n {
587                F::neg(&F::mul(&s[0][j], &d))
588            } else {
589                d.clone()
590            }
591        });
592
593        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
594            let b = &(&self.nh[x] * &t) * &s;
595            for i in 0..n {
596                for j in 0..n {
597                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
598                }
599            }
600        }
601        for (x, nh) in self.nh.iter_mut().enumerate() {
602            nh.add_col_with(|i, j| {
603                self.automaton.behavior(
604                    self.prefixes[i]
605                        .iter()
606                        .cloned()
607                        .chain([x])
608                        .chain(self.suffixes[j].iter().cloned()),
609                )
610            });
611            nh.add_row_with(|i, j| {
612                self.automaton.behavior(
613                    self.prefixes[i]
614                        .iter()
615                        .cloned()
616                        .chain([x])
617                        .chain(self.suffixes[j].iter().cloned()),
618                )
619            });
620        }
621        self.wfa
622            .initial_weights
623            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
624        self.wfa
625            .final_weights
626            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
627        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
628            transition.add_col_with(|_, _| F::zero());
629            transition.add_row_with(|_, _| F::zero());
630            for i in 0..=n {
631                for j in 0..=n {
632                    if i == n || j == n {
633                        for k in 0..=n {
634                            if i != n && j != n && k != n {
635                                continue;
636                            }
637                            F::add_assign(
638                                &mut transition[i][k],
639                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
640                            );
641                        }
642                    } else {
643                        let k = n;
644                        F::add_assign(
645                            &mut transition[i][k],
646                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
647                        );
648                    }
649                }
650            }
651        }
652        true
653    }
654    pub fn train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
655        for sample in samples {
656            self.train_sample(&sample);
657        }
658    }
659    pub fn batch_train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
660        let mut prefix_set: HashSet<_> = self.prefixes.iter().cloned().collect();
661        let mut suffix_set: HashSet<_> = self.suffixes.iter().cloned().collect();
662        for sample in samples {
663            if prefix_set.insert(sample.to_vec()) {
664                self.prefixes.push(sample.to_vec());
665            }
666            if suffix_set.insert(sample.to_vec()) {
667                self.suffixes.push(sample);
668            }
669        }
670        let mut h = Matrix::<F>::new_with((self.prefixes.len(), self.suffixes.len()), |i, j| {
671            self.automaton.behavior(
672                self.prefixes[i]
673                    .iter()
674                    .cloned()
675                    .chain(self.suffixes[j].iter().cloned()),
676            )
677        });
678        if !self.prefixes.is_empty() && !self.suffixes.is_empty() && F::is_zero(&h[0][0]) {
679            for j in 1..self.suffixes.len() {
680                if !F::is_zero(&h[0][j]) {
681                    self.suffixes.swap(0, j);
682                    for i in 0..self.prefixes.len() {
683                        h.data[i].swap(0, j);
684                    }
685                    break;
686                }
687            }
688        }
689        let mut row_id: Vec<usize> = (0..h.shape.0).collect();
690        let mut pivots = vec![];
691        h.row_reduction_with(false, |r, p, c| {
692            row_id.swap(r, p);
693            pivots.push((row_id[r], c));
694        });
695        let mut new_prefixes = vec![];
696        let mut new_suffixes = vec![];
697        for (i, j) in pivots {
698            new_prefixes.push(self.prefixes[i].clone());
699            new_suffixes.push(self.suffixes[j].clone());
700        }
701        self.prefixes = new_prefixes;
702        self.suffixes = new_suffixes;
703        assert_eq!(self.prefixes.len(), self.suffixes.len());
704        let n = self.prefixes.len();
705        let h = Matrix::<F>::new_with((n, n), |i, j| {
706            self.automaton.behavior(
707                self.prefixes[i]
708                    .iter()
709                    .cloned()
710                    .chain(self.suffixes[j].iter().cloned()),
711            )
712        });
713        self.inv_h = h.inverse().expect("Hankel matrix must be invertible");
714        self.wfa = WeightedFiniteAutomaton::<F> {
715            initial_weights: Matrix::new_with((1, n), |_, j| {
716                if self.prefixes[j].is_empty() {
717                    F::one()
718                } else {
719                    F::zero()
720                }
721            }),
722            transitions: (0..self.automaton.sigma())
723                .map(|x| {
724                    &Matrix::new_with((n, n), |i, j| {
725                        self.automaton.behavior(
726                            self.prefixes[i]
727                                .iter()
728                                .cloned()
729                                .chain([x])
730                                .chain(self.suffixes[j].iter().cloned()),
731                        )
732                    }) * &self.inv_h
733                })
734                .collect(),
735            final_weights: Matrix::new_with((n, 1), |i, _| {
736                self.automaton.behavior(self.prefixes[i].iter().cloned())
737            }),
738        };
739    }

Source

fn one() -> Self::T

multiplicative identity: $1$

Examples found in repository ?

crates/competitive/src/graph/shortest_path.rs (line 90)

89    fn source() -> Self::T {
90        PartialIgnoredOrd(M::unit(), S::one())
91    }

More examples

Hide additional examples

crates/competitive/src/algebra/ring.rs (line 31)

27    fn is_one(x: &Self::T) -> bool
28    where
29        Self::T: PartialEq,
30    {
31        *x == Self::one()
32    }

crates/competitive/src/string/rolling_hash.rs (line 508)

505    fn new(base: R::T) -> Self {
506        Self {
507            base,
508            pow: vec![R::one()],
509        }
510    }
511    fn ensure_pow(&mut self, len: usize) {
512        if self.pow.len() <= len {
513            self.pow.reserve(len - self.pow.len() + 1);
514            if self.pow.is_empty() {
515                self.pow.push(R::one());
516            }
517            for _ in 0..=len - self.pow.len() {
518                self.pow.push(R::mul(self.pow.last().unwrap(), &self.base));
519            }
520        }
521    }

crates/competitive/src/math/floor_sum.rs (line 126)

124    fn to_x() -> FloorSumData<R, X, Y> {
125        let mut dp = array![array![R::zero(); Y]; X];
126        dp[0][0] = R::one();
127        FloorSumData {
128            dp,
129            dx: R::one(),
130            dy: R::zero(),
131            _marker: PhantomData,
132        }
133    }
134    fn to_y() -> FloorSumData<R, X, Y> {
135        FloorSumData {
136            dp: array![array![R::zero(); Y]; X],
137            dx: R::zero(),
138            dy: R::one(),
139            _marker: PhantomData,
140        }
141    }
142}
143
144impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>
145where
146    R: Ring,
147    R::Additive: Invertible,
148{
149    fn offset(x: i64, y: i64) -> FloorSumData<R, X, Y> {
150        FloorSumData {
151            dp: array![array![R::zero(); Y]; X],
152            dx: R::Additive::signed_pow(R::one(), x),
153            dy: R::Additive::signed_pow(R::one(), y),
154            _marker: PhantomData,
155        }
156    }
157}
158
159impl<R, const X: usize, const Y: usize> Magma for FloorSum<R, X, Y>
160where
161    R: SemiRing,
162{
163    type T = FloorSumData<R, X, Y>;
164
165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }

crates/competitive/src/math/matrix.rs (line 105)

102    pub fn eye(shape: (usize, usize)) -> Self {
103        let mut data = vec![vec![R::zero(); shape.1]; shape.0];
104        for (i, d) in data.iter_mut().enumerate().take(shape.1) {
105            d[i] = R::one();
106        }
107        Self {
108            shape,
109            data,
110            _marker: PhantomData,
111        }
112    }
113
114    pub fn transpose(&self) -> Self {
115        Self::new_with((self.shape.1, self.shape.0), |i, j| self[j][i].clone())
116    }
117
118    pub fn map<S, F>(&self, mut f: F) -> Matrix<S>
119    where
120        S: SemiRing,
121        F: FnMut(&R::T) -> S::T,
122    {
123        Matrix::<S>::new_with(self.shape, |i, j| f(&self[i][j]))
124    }
125
126    pub fn add_row_with(&mut self, mut f: impl FnMut(usize, usize) -> R::T) {
127        self.data
128            .push((0..self.shape.1).map(|j| f(self.shape.0, j)).collect());
129        self.shape.0 += 1;
130    }
131
132    pub fn add_col_with(&mut self, mut f: impl FnMut(usize, usize) -> R::T) {
133        for i in 0..self.shape.0 {
134            self.data[i].push(f(i, self.shape.1));
135        }
136        self.shape.1 += 1;
137    }
138
139    pub fn pairwise_assign<F>(&mut self, other: &Self, mut f: F)
140    where
141        F: FnMut(&mut R::T, &R::T),
142    {
143        assert_eq!(self.shape, other.shape);
144        for i in 0..self.shape.0 {
145            for j in 0..self.shape.1 {
146                f(&mut self[i][j], &other[i][j]);
147            }
148        }
149    }
150}
151
152#[derive(Debug)]
153pub struct SystemOfLinearEquationsSolution<R>
154where
155    R: Field,
156    R::Additive: Invertible,
157    R::Multiplicative: Invertible,
158{
159    pub particular: Vec<R::T>,
160    pub basis: Vec<Vec<R::T>>,
161}
162
163impl<R> Matrix<R>
164where
165    R: Field,
166    R::Additive: Invertible,
167    R::Multiplicative: Invertible,
168    R::T: PartialEq,
169{
170    /// f: (row, pivot_row, col)
171    pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
172    where
173        F: FnMut(usize, usize, usize),
174    {
175        let (n, m) = self.shape;
176        let mut c = 0;
177        for r in 0..n {
178            loop {
179                if c >= m {
180                    return;
181                }
182                if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
183                    f(r, pivot, c);
184                    self.data.swap(r, pivot);
185                    break;
186                };
187                c += 1;
188            }
189            let d = R::inv(&self[r][c]);
190            if normalize {
191                for j in c..m {
192                    R::mul_assign(&mut self[r][j], &d);
193                }
194            }
195            for i in (0..n).filter(|&i| i != r) {
196                let mut e = self[i][c].clone();
197                if !normalize {
198                    R::mul_assign(&mut e, &d);
199                }
200                for j in c..m {
201                    let e = R::mul(&e, &self[r][j]);
202                    R::sub_assign(&mut self[i][j], &e);
203                }
204            }
205            c += 1;
206        }
207    }
208
209    pub fn row_reduction(&mut self, normalize: bool) {
210        self.row_reduction_with(normalize, |_, _, _| {});
211    }
212
213    pub fn rank(&mut self) -> usize {
214        let n = self.shape.0;
215        self.row_reduction(false);
216        (0..n)
217            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
218            .count()
219    }
220
221    pub fn determinant(&mut self) -> R::T {
222        assert_eq!(self.shape.0, self.shape.1);
223        let mut neg = false;
224        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
225        let mut d = R::one();
226        if neg {
227            d = R::neg(&d);
228        }
229        for i in 0..self.shape.0 {
230            R::mul_assign(&mut d, &self[i][i]);
231        }
232        d
233    }
234
235    pub fn solve_system_of_linear_equations(
236        &self,
237        b: &[R::T],
238    ) -> Option<SystemOfLinearEquationsSolution<R>> {
239        assert_eq!(self.shape.0, b.len());
240        let (n, m) = self.shape;
241        let mut c = Matrix::<R>::zeros((n, m + 1));
242        for i in 0..n {
243            c[i][..m].clone_from_slice(&self[i]);
244            c[i][m] = b[i].clone();
245        }
246        let mut reduced = vec![!0; m + 1];
247        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
248        if reduced[m] != !0 {
249            return None;
250        }
251        let mut particular = vec![R::zero(); m];
252        let mut basis = vec![];
253        for j in 0..m {
254            if reduced[j] != !0 {
255                particular[j] = c[reduced[j]][m].clone();
256            } else {
257                let mut v = vec![R::zero(); m];
258                v[j] = R::one();
259                for i in 0..m {
260                    if reduced[i] != !0 {
261                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
262                    }
263                }
264                basis.push(v);
265            }
266        }
267        Some(SystemOfLinearEquationsSolution { particular, basis })
268    }
269
270    pub fn inverse(&self) -> Option<Matrix<R>> {
271        assert_eq!(self.shape.0, self.shape.1);
272        let n = self.shape.0;
273        let mut c = Matrix::<R>::zeros((n, n * 2));
274        for i in 0..n {
275            c[i][..n].clone_from_slice(&self[i]);
276            c[i][n + i] = R::one();
277        }
278        c.row_reduction(true);
279        if (0..n).any(|i| R::is_zero(&c[i][i])) {
280            None
281        } else {
282            Some(Self::from_vec(
283                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
284            ))
285        }
286    }
287
288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }

crates/competitive/src/algorithm/automata_learning.rs (line 623)

545    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
546        let Some((prefix, suffix)) = self.split_sample(sample) else {
547            return false;
548        };
549        self.prefixes.push(prefix);
550        self.suffixes.push(suffix);
551        let n = self.inv_h.shape.0;
552        let prefix = &self.prefixes[n];
553        let suffix = &self.suffixes[n];
554        let u = Matrix::<F>::new_with((n, 1), |i, _| {
555            self.automaton.behavior(
556                self.prefixes[i]
557                    .iter()
558                    .cloned()
559                    .chain(suffix.iter().cloned()),
560            )
561        });
562        let v = Matrix::<F>::new_with((1, n), |_, j| {
563            self.automaton.behavior(
564                prefix
565                    .iter()
566                    .cloned()
567                    .chain(self.suffixes[j].iter().cloned()),
568            )
569        });
570        let w = Matrix::<F>::new_with((1, 1), |_, _| {
571            self.automaton
572                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
573        });
574        let t = &self.inv_h * &u;
575        let s = &v * &self.inv_h;
576        let d = F::inv(&(&w - &(&v * &t))[0][0]);
577        let dh = &t * &s;
578        for i in 0..n {
579            for j in 0..n {
580                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
581            }
582        }
583        self.inv_h
584            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
585        self.inv_h.add_row_with(|_, j| {
586            if j != n {
587                F::neg(&F::mul(&s[0][j], &d))
588            } else {
589                d.clone()
590            }
591        });
592
593        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
594            let b = &(&self.nh[x] * &t) * &s;
595            for i in 0..n {
596                for j in 0..n {
597                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
598                }
599            }
600        }
601        for (x, nh) in self.nh.iter_mut().enumerate() {
602            nh.add_col_with(|i, j| {
603                self.automaton.behavior(
604                    self.prefixes[i]
605                        .iter()
606                        .cloned()
607                        .chain([x])
608                        .chain(self.suffixes[j].iter().cloned()),
609                )
610            });
611            nh.add_row_with(|i, j| {
612                self.automaton.behavior(
613                    self.prefixes[i]
614                        .iter()
615                        .cloned()
616                        .chain([x])
617                        .chain(self.suffixes[j].iter().cloned()),
618                )
619            });
620        }
621        self.wfa
622            .initial_weights
623            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
624        self.wfa
625            .final_weights
626            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
627        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
628            transition.add_col_with(|_, _| F::zero());
629            transition.add_row_with(|_, _| F::zero());
630            for i in 0..=n {
631                for j in 0..=n {
632                    if i == n || j == n {
633                        for k in 0..=n {
634                            if i != n && j != n && k != n {
635                                continue;
636                            }
637                            F::add_assign(
638                                &mut transition[i][k],
639                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
640                            );
641                        }
642                    } else {
643                        let k = n;
644                        F::add_assign(
645                            &mut transition[i][k],
646                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
647                        );
648                    }
649                }
650            }
651        }
652        true
653    }
654    pub fn train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
655        for sample in samples {
656            self.train_sample(&sample);
657        }
658    }
659    pub fn batch_train(&mut self, samples: impl IntoIterator<Item = Vec<usize>>) {
660        let mut prefix_set: HashSet<_> = self.prefixes.iter().cloned().collect();
661        let mut suffix_set: HashSet<_> = self.suffixes.iter().cloned().collect();
662        for sample in samples {
663            if prefix_set.insert(sample.to_vec()) {
664                self.prefixes.push(sample.to_vec());
665            }
666            if suffix_set.insert(sample.to_vec()) {
667                self.suffixes.push(sample);
668            }
669        }
670        let mut h = Matrix::<F>::new_with((self.prefixes.len(), self.suffixes.len()), |i, j| {
671            self.automaton.behavior(
672                self.prefixes[i]
673                    .iter()
674                    .cloned()
675                    .chain(self.suffixes[j].iter().cloned()),
676            )
677        });
678        if !self.prefixes.is_empty() && !self.suffixes.is_empty() && F::is_zero(&h[0][0]) {
679            for j in 1..self.suffixes.len() {
680                if !F::is_zero(&h[0][j]) {
681                    self.suffixes.swap(0, j);
682                    for i in 0..self.prefixes.len() {
683                        h.data[i].swap(0, j);
684                    }
685                    break;
686                }
687            }
688        }
689        let mut row_id: Vec<usize> = (0..h.shape.0).collect();
690        let mut pivots = vec![];
691        h.row_reduction_with(false, |r, p, c| {
692            row_id.swap(r, p);
693            pivots.push((row_id[r], c));
694        });
695        let mut new_prefixes = vec![];
696        let mut new_suffixes = vec![];
697        for (i, j) in pivots {
698            new_prefixes.push(self.prefixes[i].clone());
699            new_suffixes.push(self.suffixes[j].clone());
700        }
701        self.prefixes = new_prefixes;
702        self.suffixes = new_suffixes;
703        assert_eq!(self.prefixes.len(), self.suffixes.len());
704        let n = self.prefixes.len();
705        let h = Matrix::<F>::new_with((n, n), |i, j| {
706            self.automaton.behavior(
707                self.prefixes[i]
708                    .iter()
709                    .cloned()
710                    .chain(self.suffixes[j].iter().cloned()),
711            )
712        });
713        self.inv_h = h.inverse().expect("Hankel matrix must be invertible");
714        self.wfa = WeightedFiniteAutomaton::<F> {
715            initial_weights: Matrix::new_with((1, n), |_, j| {
716                if self.prefixes[j].is_empty() {
717                    F::one()
718                } else {
719                    F::zero()
720                }
721            }),
722            transitions: (0..self.automaton.sigma())
723                .map(|x| {
724                    &Matrix::new_with((n, n), |i, j| {
725                        self.automaton.behavior(
726                            self.prefixes[i]
727                                .iter()
728                                .cloned()
729                                .chain([x])
730                                .chain(self.suffixes[j].iter().cloned()),
731                        )
732                    }) * &self.inv_h
733                })
734                .collect(),
735            final_weights: Matrix::new_with((n, 1), |i, _| {
736                self.automaton.behavior(self.prefixes[i].iter().cloned())
737            }),
738        };
739    }

Source

fn is_one(x: &Self::T) -> bool
where Self::T: PartialEq,

checks if the element is one

Source

fn add(x: &Self::T, y: &Self::T) -> Self::T

additive operaion: $+$

Examples found in repository ?

crates/competitive/src/string/rolling_hash.rs (line 523)

522    fn mul1_add(&self, x: &R::T, y: &R::T) -> R::T {
523        R::add(&R::mul(x, &self.base), y)
524    }
525    fn muln_add(&mut self, x: &R::T, y: &R::T, n: usize) -> R::T {
526        if let Some(pow) = self.pow.get(n) {
527            R::add(&R::mul(x, pow), y)
528        } else {
529            let pow = <R::Multiplicative as Monoid>::pow(self.base.clone(), n);
530            R::add(&R::mul(x, &pow), y)
531        }
532    }

More examples

Hide additional examples

crates/competitive/src/graph/shortest_path.rs (line 101)

98    fn add_assign(x: &mut Self::T, y: &Self::T) -> bool {
99        match x.0.cmp(&y.0) {
100            Ordering::Equal => {
101                x.1 = S::add(&x.1, &y.1);
102                false
103            }
104            Ordering::Greater => {
105                *x = y.clone();
106                true
107            }
108            _ => false,
109        }
110    }

crates/competitive/src/math/subset_convolve.rs (line 26)

21    fn transform(t: Self::T, len: usize) -> Self::F {
22        let k = len.trailing_zeros() as usize;
23        let mut f = vec![vec![R::zero(); len]; k + 1];
24        for (i, t) in t.iter().enumerate() {
25            let f = &mut f[i.count_ones() as usize][i];
26            *f = R::add(f, t);
27        }
28        for f in f.iter_mut() {
29            BitwiseorConvolve::<R::Additive>::zeta_transform(f);
30        }
31        f
32    }
33
34    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
35        for f in f.iter_mut() {
36            BitwiseorConvolve::<R::Additive>::mobius_transform(f);
37        }
38        let mut t = vec![R::zero(); len];
39        for (i, t) in t.iter_mut().enumerate() {
40            *t = R::add(t, &f[i.count_ones() as usize][i]);
41        }
42        t
43    }
44
45    fn multiply(f: &mut Self::F, g: &Self::F) {
46        for i in (0..f.len()).rev() {
47            let (lf, rf) = f.split_at_mut(i);
48            for (x, y) in rf[0].iter_mut().zip(&g[0]) {
49                *x = R::mul(x, y);
50            }
51            for (x, y) in lf.iter().rev().zip(g.iter().skip(1)) {
52                for ((x, y), z) in x.iter().zip(y).zip(&mut rf[0]) {
53                    *z = R::add(z, &R::mul(x, y));
54                }
55            }
56        }
57    }

crates/competitive/src/algorithm/esper.rs (line 150)

138    pub fn solve(&self, input: Input) -> R::T {
139        let coeff = self
140            .data
141            .get(&(self.class)(&input))
142            .expect("unrecognized class")
143            .as_ref()
144            .expect("failed to solve");
145        let feature = (self.feature)(&input);
146        feature
147            .into_iter()
148            .zip(coeff)
149            .map(|(x, y)| R::mul(&x, y))
150            .fold(R::zero(), |x, y| R::add(&x, &y))
151    }

crates/competitive/src/math/quotient_array.rs (line 100)

82    pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
83    where
84        T: Clone + One,
85        R: Ring<T = T>,
86        R::Additive: Invertible,
87    {
88        let mut dp = self.clone();
89        with_prime_list(self.isqrtn, |pl| {
90            for &p in pl.primes_lte(self.isqrtn).iter().rev() {
91                let k = self.quotient_index(p);
92                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
93                    let mut pc = p;
94                    if pc * p > q {
95                        break;
96                    }
97                    let mut c = 1;
98                    while q / p >= pc {
99                        let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
100                        let x = R::add(&x, &f(p, c + 1));
101                        dp.data[i] = R::add(&dp.data[i], &x);
102                        c += 1;
103                        pc *= p;
104                    }
105                }
106            }
107        });
108        for x in &mut dp.data {
109            *x = R::add(x, &T::one());
110        }
111        dp
112    }

crates/competitive/src/math/matrix.rs (line 313)

288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }

Source

fn mul(x: &Self::T, y: &Self::T) -> Self::T

multiplicative operaion: $+$

Examples found in repository ?

crates/competitive/src/graph/shortest_path.rs (line 96)

95    fn mul(x: &Self::T, y: &Self::T) -> Self::T {
96        PartialIgnoredOrd(M::operate(&x.0, &y.0), S::mul(&x.1, &y.1))
97    }

More examples

Hide additional examples

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

51    fn multiply(f: &mut Self::F, g: &Self::F) {
52        for (f, g) in f.iter_mut().zip(g) {
53            *f = R::mul(f, g);
54        }
55    }
56
57    fn convolve(a: Self::T, b: Self::T) -> Self::T {
58        assert_eq!(a.len(), b.len());
59        let len = a.len();
60        let same = a == b;
61        let mut a = Self::transform(a, len);
62        if same {
63            for a in a.iter_mut() {
64                *a = R::mul(a, a);
65            }
66        } else {
67            let b = Self::transform(b, len);
68            Self::multiply(&mut a, &b);
69        }
70        Self::inverse_transform(a, len)
71    }

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

51    fn multiply(f: &mut Self::F, g: &Self::F) {
52        for (f, g) in f.iter_mut().zip(g) {
53            *f = R::mul(f, g);
54        }
55    }
56
57    fn convolve(a: Self::T, b: Self::T) -> Self::T {
58        assert_eq!(a.len(), b.len());
59        let len = a.len();
60        let same = a == b;
61        let mut a = Self::transform(a, len);
62        if same {
63            for a in a.iter_mut() {
64                *a = R::mul(a, a);
65            }
66        } else {
67            let b = Self::transform(b, len);
68            Self::multiply(&mut a, &b);
69        }
70        Self::inverse_transform(a, len)
71    }

crates/competitive/src/math/bitwisexor_convolve.rs (line 52)

50    fn multiply(f: &mut Self::F, g: &Self::F) {
51        for (f, g) in f.iter_mut().zip(g) {
52            *f = R::mul(f, g);
53        }
54    }
55
56    fn convolve(a: Self::T, b: Self::T) -> Self::T {
57        assert_eq!(a.len(), b.len());
58        let len = a.len();
59        let same = a == b;
60        let mut a = Self::transform(a, len);
61        if same {
62            for a in a.iter_mut() {
63                *a = R::mul(a, a);
64            }
65        } else {
66            let b = Self::transform(b, len);
67            Self::multiply(&mut a, &b);
68        }
69        Self::inverse_transform(a, len)
70    }
71}
72
73impl<R> ConvolveSteps for BitwisexorConvolve<R, true>
74where
75    R: Field,
76    R::T: PartialEq,
77    R::Additive: Invertible,
78    R::Multiplicative: Invertible,
79    R::T: TryFrom<usize>,
80    <R::T as TryFrom<usize>>::Error: Debug,
81{
82    type T = Vec<R::T>;
83    type F = Vec<R::T>;
84
85    fn length(t: &Self::T) -> usize {
86        t.len()
87    }
88
89    fn transform(mut t: Self::T, _len: usize) -> Self::F {
90        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut t);
91        t
92    }
93
94    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
95        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut f);
96        let len = R::T::try_from(len).unwrap();
97        for f in f.iter_mut() {
98            *f = R::div(f, &len);
99        }
100        f
101    }
102
103    fn multiply(f: &mut Self::F, g: &Self::F) {
104        for (f, g) in f.iter_mut().zip(g) {
105            *f = R::mul(f, g);
106        }
107    }
108
109    fn convolve(a: Self::T, b: Self::T) -> Self::T {
110        assert_eq!(a.len(), b.len());
111        let len = a.len();
112        let same = a == b;
113        let mut a = Self::transform(a, len);
114        if same {
115            for a in a.iter_mut() {
116                *a = R::mul(a, a);
117            }
118        } else {
119            let b = Self::transform(b, len);
120            Self::multiply(&mut a, &b);
121        }
122        Self::inverse_transform(a, len)
123    }

crates/competitive/src/math/gcd_convolve.rs (line 66)

64    fn multiply(f: &mut Self::F, g: &Self::F) {
65        for (f, g) in f.iter_mut().zip(g) {
66            *f = R::mul(f, g);
67        }
68    }

crates/competitive/src/math/lcm_convolve.rs (line 66)

64    fn multiply(f: &mut Self::F, g: &Self::F) {
65        for (f, g) in f.iter_mut().zip(g) {
66            *f = R::mul(f, g);
67        }
68    }

Additional examples can be found in:

Source

fn add_assign(x: &mut Self::T, y: &Self::T)

Examples found in repository ?

crates/competitive/src/math/black_box_matrix.rs (line 28)

23    fn apply(&self, v: &[R::T]) -> Vec<R::T> {
24        assert_eq!(self.shape.1, v.len());
25        let mut res = vec![R::zero(); self.shape.0];
26        for i in 0..self.shape.0 {
27            for j in 0..self.shape.1 {
28                R::add_assign(&mut res[i], &R::mul(&self[(i, j)], &v[j]));
29            }
30        }
31        res
32    }
33
34    fn shape(&self) -> (usize, usize) {
35        self.shape
36    }
37}
38
39pub struct SparseMatrix<R>
40where
41    R: SemiRing,
42{
43    shape: (usize, usize),
44    nonzero: Vec<(usize, usize, R::T)>,
45}
46
47impl<R> Debug for SparseMatrix<R>
48where
49    R: SemiRing,
50    R::T: Debug,
51{
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        f.debug_struct("SparseMatrix")
54            .field("shape", &self.shape)
55            .field("nonzero", &self.nonzero)
56            .finish()
57    }
58}
59
60impl<R> Clone for SparseMatrix<R>
61where
62    R: SemiRing,
63{
64    fn clone(&self) -> Self {
65        Self {
66            shape: self.shape,
67            nonzero: self.nonzero.clone(),
68        }
69    }
70}
71
72impl<R> SparseMatrix<R>
73where
74    R: SemiRing,
75{
76    pub fn new(shape: (usize, usize)) -> Self {
77        Self {
78            shape,
79            nonzero: vec![],
80        }
81    }
82    pub fn new_with<F>(shape: (usize, usize), f: F) -> Self
83    where
84        R::T: PartialEq,
85        F: Fn(usize, usize) -> R::T,
86    {
87        let mut nonzero = vec![];
88        for i in 0..shape.0 {
89            for j in 0..shape.1 {
90                let v = f(i, j);
91                if !R::is_zero(&v) {
92                    nonzero.push((i, j, v));
93                }
94            }
95        }
96        Self { shape, nonzero }
97    }
98    pub fn from_nonzero(shape: (usize, usize), nonzero: Vec<(usize, usize, R::T)>) -> Self {
99        Self { shape, nonzero }
100    }
101}
102
103impl<R> From<Matrix<R>> for SparseMatrix<R>
104where
105    R: SemiRing,
106    R::T: PartialEq,
107{
108    fn from(mat: Matrix<R>) -> Self {
109        let mut nonzero = vec![];
110        for i in 0..mat.shape.0 {
111            for j in 0..mat.shape.1 {
112                let v = mat[(i, j)].clone();
113                if !R::is_zero(&v) {
114                    nonzero.push((i, j, v));
115                }
116            }
117        }
118        Self {
119            shape: mat.shape,
120            nonzero,
121        }
122    }
123}
124
125impl<R> From<SparseMatrix<R>> for Matrix<R>
126where
127    R: SemiRing,
128{
129    fn from(smat: SparseMatrix<R>) -> Self {
130        let mut mat = Matrix::zeros(smat.shape);
131        for &(i, j, ref v) in &smat.nonzero {
132            R::add_assign(&mut mat[(i, j)], v);
133        }
134        mat
135    }
136}
137
138impl<R> BlackBoxMatrix<R> for SparseMatrix<R>
139where
140    R: SemiRing,
141{
142    fn apply(&self, v: &[R::T]) -> Vec<R::T> {
143        assert_eq!(self.shape.1, v.len());
144        let mut res = vec![R::zero(); self.shape.0];
145        for &(i, j, ref val) in &self.nonzero {
146            R::add_assign(&mut res[i], &R::mul(val, &v[j]));
147        }
148        res
149    }

More examples

Hide additional examples

crates/competitive/src/math/matrix.rs (line 314)

288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }
337}
338
339impl<R> Index<usize> for Matrix<R>
340where
341    R: SemiRing,
342{
343    type Output = Vec<R::T>;
344    fn index(&self, index: usize) -> &Self::Output {
345        &self.data[index]
346    }
347}
348
349impl<R> IndexMut<usize> for Matrix<R>
350where
351    R: SemiRing,
352{
353    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
354        &mut self.data[index]
355    }
356}
357
358impl<R> Index<(usize, usize)> for Matrix<R>
359where
360    R: SemiRing,
361{
362    type Output = R::T;
363    fn index(&self, index: (usize, usize)) -> &Self::Output {
364        &self.data[index.0][index.1]
365    }
366}
367
368impl<R> IndexMut<(usize, usize)> for Matrix<R>
369where
370    R: SemiRing,
371{
372    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
373        &mut self.data[index.0][index.1]
374    }
375}
376
377macro_rules! impl_matrix_pairwise_binop {
378    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident $(where [$($clauses:tt)*])?) => {
379        impl<R> $imp_assign for Matrix<R>
380        where
381            R: SemiRing,
382            $($($clauses)*)?
383        {
384            fn $method_assign(&mut self, rhs: Self) {
385                self.pairwise_assign(&rhs, |a, b| R::$method_assign(a, b));
386            }
387        }
388        impl<R> $imp_assign<&Matrix<R>> for Matrix<R>
389        where
390            R: SemiRing,
391            $($($clauses)*)?
392        {
393            fn $method_assign(&mut self, rhs: &Self) {
394                self.pairwise_assign(rhs, |a, b| R::$method_assign(a, b));
395            }
396        }
397        impl<R> $imp for Matrix<R>
398        where
399            R: SemiRing,
400            $($($clauses)*)?
401        {
402            type Output = Matrix<R>;
403            fn $method(mut self, rhs: Self) -> Self::Output {
404                self.$method_assign(rhs);
405                self
406            }
407        }
408        impl<R> $imp<&Matrix<R>> for Matrix<R>
409        where
410            R: SemiRing,
411            $($($clauses)*)?
412        {
413            type Output = Matrix<R>;
414            fn $method(mut self, rhs: &Self) -> Self::Output {
415                self.$method_assign(rhs);
416                self
417            }
418        }
419        impl<R> $imp<Matrix<R>> for &Matrix<R>
420        where
421            R: SemiRing,
422            $($($clauses)*)?
423        {
424            type Output = Matrix<R>;
425            fn $method(self, mut rhs: Matrix<R>) -> Self::Output {
426                rhs.pairwise_assign(self, |a, b| *a = R::$method(b, a));
427                rhs
428            }
429        }
430        impl<R> $imp<&Matrix<R>> for &Matrix<R>
431        where
432            R: SemiRing,
433            $($($clauses)*)?
434        {
435            type Output = Matrix<R>;
436            fn $method(self, rhs: &Matrix<R>) -> Self::Output {
437                let mut this = self.clone();
438                this.$method_assign(rhs);
439                this
440            }
441        }
442    };
443}
444
445impl_matrix_pairwise_binop!(Add, add, AddAssign, add_assign);
446impl_matrix_pairwise_binop!(Sub, sub, SubAssign, sub_assign where [R::Additive: Invertible]);
447
448impl<R> Mul for Matrix<R>
449where
450    R: SemiRing,
451{
452    type Output = Matrix<R>;
453    fn mul(self, rhs: Self) -> Self::Output {
454        (&self).mul(&rhs)
455    }
456}
457impl<R> Mul<&Matrix<R>> for Matrix<R>
458where
459    R: SemiRing,
460{
461    type Output = Matrix<R>;
462    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
463        (&self).mul(rhs)
464    }
465}
466impl<R> Mul<Matrix<R>> for &Matrix<R>
467where
468    R: SemiRing,
469{
470    type Output = Matrix<R>;
471    fn mul(self, rhs: Matrix<R>) -> Self::Output {
472        self.mul(&rhs)
473    }
474}
475impl<R> Mul<&Matrix<R>> for &Matrix<R>
476where
477    R: SemiRing,
478{
479    type Output = Matrix<R>;
480    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
481        assert_eq!(self.shape.1, rhs.shape.0);
482        let mut res = Matrix::zeros((self.shape.0, rhs.shape.1));
483        for i in 0..self.shape.0 {
484            for k in 0..self.shape.1 {
485                for j in 0..rhs.shape.1 {
486                    R::add_assign(&mut res[i][j], &R::mul(&self[i][k], &rhs[k][j]));
487                }
488            }
489        }
490        res
491    }

crates/competitive/src/math/floor_sum.rs (line 220)

165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }

crates/competitive/src/algorithm/automata_learning.rs (line 580)

545    pub fn train_sample(&mut self, sample: &[usize]) -> bool {
546        let Some((prefix, suffix)) = self.split_sample(sample) else {
547            return false;
548        };
549        self.prefixes.push(prefix);
550        self.suffixes.push(suffix);
551        let n = self.inv_h.shape.0;
552        let prefix = &self.prefixes[n];
553        let suffix = &self.suffixes[n];
554        let u = Matrix::<F>::new_with((n, 1), |i, _| {
555            self.automaton.behavior(
556                self.prefixes[i]
557                    .iter()
558                    .cloned()
559                    .chain(suffix.iter().cloned()),
560            )
561        });
562        let v = Matrix::<F>::new_with((1, n), |_, j| {
563            self.automaton.behavior(
564                prefix
565                    .iter()
566                    .cloned()
567                    .chain(self.suffixes[j].iter().cloned()),
568            )
569        });
570        let w = Matrix::<F>::new_with((1, 1), |_, _| {
571            self.automaton
572                .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
573        });
574        let t = &self.inv_h * &u;
575        let s = &v * &self.inv_h;
576        let d = F::inv(&(&w - &(&v * &t))[0][0]);
577        let dh = &t * &s;
578        for i in 0..n {
579            for j in 0..n {
580                F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
581            }
582        }
583        self.inv_h
584            .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
585        self.inv_h.add_row_with(|_, j| {
586            if j != n {
587                F::neg(&F::mul(&s[0][j], &d))
588            } else {
589                d.clone()
590            }
591        });
592
593        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
594            let b = &(&self.nh[x] * &t) * &s;
595            for i in 0..n {
596                for j in 0..n {
597                    F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
598                }
599            }
600        }
601        for (x, nh) in self.nh.iter_mut().enumerate() {
602            nh.add_col_with(|i, j| {
603                self.automaton.behavior(
604                    self.prefixes[i]
605                        .iter()
606                        .cloned()
607                        .chain([x])
608                        .chain(self.suffixes[j].iter().cloned()),
609                )
610            });
611            nh.add_row_with(|i, j| {
612                self.automaton.behavior(
613                    self.prefixes[i]
614                        .iter()
615                        .cloned()
616                        .chain([x])
617                        .chain(self.suffixes[j].iter().cloned()),
618                )
619            });
620        }
621        self.wfa
622            .initial_weights
623            .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
624        self.wfa
625            .final_weights
626            .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
627        for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
628            transition.add_col_with(|_, _| F::zero());
629            transition.add_row_with(|_, _| F::zero());
630            for i in 0..=n {
631                for j in 0..=n {
632                    if i == n || j == n {
633                        for k in 0..=n {
634                            if i != n && j != n && k != n {
635                                continue;
636                            }
637                            F::add_assign(
638                                &mut transition[i][k],
639                                &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
640                            );
641                        }
642                    } else {
643                        let k = n;
644                        F::add_assign(
645                            &mut transition[i][k],
646                            &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
647                        );
648                    }
649                }
650            }
651        }
652        true
653    }

Source

fn mul_assign(x: &mut Self::T, y: &Self::T)

Examples found in repository ?

crates/competitive/src/math/matrix.rs (line 192)

171    pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
172    where
173        F: FnMut(usize, usize, usize),
174    {
175        let (n, m) = self.shape;
176        let mut c = 0;
177        for r in 0..n {
178            loop {
179                if c >= m {
180                    return;
181                }
182                if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
183                    f(r, pivot, c);
184                    self.data.swap(r, pivot);
185                    break;
186                };
187                c += 1;
188            }
189            let d = R::inv(&self[r][c]);
190            if normalize {
191                for j in c..m {
192                    R::mul_assign(&mut self[r][j], &d);
193                }
194            }
195            for i in (0..n).filter(|&i| i != r) {
196                let mut e = self[i][c].clone();
197                if !normalize {
198                    R::mul_assign(&mut e, &d);
199                }
200                for j in c..m {
201                    let e = R::mul(&e, &self[r][j]);
202                    R::sub_assign(&mut self[i][j], &e);
203                }
204            }
205            c += 1;
206        }
207    }
208
209    pub fn row_reduction(&mut self, normalize: bool) {
210        self.row_reduction_with(normalize, |_, _, _| {});
211    }
212
213    pub fn rank(&mut self) -> usize {
214        let n = self.shape.0;
215        self.row_reduction(false);
216        (0..n)
217            .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
218            .count()
219    }
220
221    pub fn determinant(&mut self) -> R::T {
222        assert_eq!(self.shape.0, self.shape.1);
223        let mut neg = false;
224        self.row_reduction_with(false, |r, p, _| neg ^= r != p);
225        let mut d = R::one();
226        if neg {
227            d = R::neg(&d);
228        }
229        for i in 0..self.shape.0 {
230            R::mul_assign(&mut d, &self[i][i]);
231        }
232        d
233    }
234
235    pub fn solve_system_of_linear_equations(
236        &self,
237        b: &[R::T],
238    ) -> Option<SystemOfLinearEquationsSolution<R>> {
239        assert_eq!(self.shape.0, b.len());
240        let (n, m) = self.shape;
241        let mut c = Matrix::<R>::zeros((n, m + 1));
242        for i in 0..n {
243            c[i][..m].clone_from_slice(&self[i]);
244            c[i][m] = b[i].clone();
245        }
246        let mut reduced = vec![!0; m + 1];
247        c.row_reduction_with(true, |r, _, c| reduced[c] = r);
248        if reduced[m] != !0 {
249            return None;
250        }
251        let mut particular = vec![R::zero(); m];
252        let mut basis = vec![];
253        for j in 0..m {
254            if reduced[j] != !0 {
255                particular[j] = c[reduced[j]][m].clone();
256            } else {
257                let mut v = vec![R::zero(); m];
258                v[j] = R::one();
259                for i in 0..m {
260                    if reduced[i] != !0 {
261                        R::sub_assign(&mut v[i], &c[reduced[i]][j]);
262                    }
263                }
264                basis.push(v);
265            }
266        }
267        Some(SystemOfLinearEquationsSolution { particular, basis })
268    }
269
270    pub fn inverse(&self) -> Option<Matrix<R>> {
271        assert_eq!(self.shape.0, self.shape.1);
272        let n = self.shape.0;
273        let mut c = Matrix::<R>::zeros((n, n * 2));
274        for i in 0..n {
275            c[i][..n].clone_from_slice(&self[i]);
276            c[i][n + i] = R::one();
277        }
278        c.row_reduction(true);
279        if (0..n).any(|i| R::is_zero(&c[i][i])) {
280            None
281        } else {
282            Some(Self::from_vec(
283                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
284            ))
285        }
286    }
287
288    pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
289        let n = self.shape.0;
290        if n == 0 {
291            return vec![R::one()];
292        }
293        assert!(self.data.iter().all(|a| a.len() == n));
294        for j in 0..(n - 1) {
295            if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
296                self.data.swap(j + 1, x);
297                self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
298                let inv = R::inv(&self[j + 1][j]);
299                let mut v = vec![];
300                let src = std::mem::take(&mut self[j + 1]);
301                for a in self.data[(j + 2)..].iter_mut() {
302                    let mul = R::mul(&a[j], &inv);
303                    for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
304                        R::sub_assign(a, &R::mul(&mul, src));
305                    }
306                    v.push(mul);
307                }
308                self[j + 1] = src;
309                for a in self.data.iter_mut() {
310                    let v = a[(j + 2)..]
311                        .iter()
312                        .zip(v.iter())
313                        .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
314                    R::add_assign(&mut a[j + 1], &v);
315                }
316            }
317        }
318        let mut dp = vec![vec![R::one()]];
319        for i in 0..n {
320            let mut next = vec![R::zero(); i + 2];
321            for (j, dp) in dp[i].iter().enumerate() {
322                R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
323                R::add_assign(&mut next[j + 1], dp);
324            }
325            let mut mul = R::one();
326            for j in (0..i).rev() {
327                mul = R::mul(&mul, &self[j + 1][j]);
328                let c = R::mul(&mul, &self[j][i]);
329                for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
330                    R::sub_assign(next, &R::mul(&c, dp));
331                }
332            }
333            dp.push(next);
334        }
335        dp.pop().unwrap()
336    }
337}
338
339impl<R> Index<usize> for Matrix<R>
340where
341    R: SemiRing,
342{
343    type Output = Vec<R::T>;
344    fn index(&self, index: usize) -> &Self::Output {
345        &self.data[index]
346    }
347}
348
349impl<R> IndexMut<usize> for Matrix<R>
350where
351    R: SemiRing,
352{
353    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
354        &mut self.data[index]
355    }
356}
357
358impl<R> Index<(usize, usize)> for Matrix<R>
359where
360    R: SemiRing,
361{
362    type Output = R::T;
363    fn index(&self, index: (usize, usize)) -> &Self::Output {
364        &self.data[index.0][index.1]
365    }
366}
367
368impl<R> IndexMut<(usize, usize)> for Matrix<R>
369where
370    R: SemiRing,
371{
372    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
373        &mut self.data[index.0][index.1]
374    }
375}
376
377macro_rules! impl_matrix_pairwise_binop {
378    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident $(where [$($clauses:tt)*])?) => {
379        impl<R> $imp_assign for Matrix<R>
380        where
381            R: SemiRing,
382            $($($clauses)*)?
383        {
384            fn $method_assign(&mut self, rhs: Self) {
385                self.pairwise_assign(&rhs, |a, b| R::$method_assign(a, b));
386            }
387        }
388        impl<R> $imp_assign<&Matrix<R>> for Matrix<R>
389        where
390            R: SemiRing,
391            $($($clauses)*)?
392        {
393            fn $method_assign(&mut self, rhs: &Self) {
394                self.pairwise_assign(rhs, |a, b| R::$method_assign(a, b));
395            }
396        }
397        impl<R> $imp for Matrix<R>
398        where
399            R: SemiRing,
400            $($($clauses)*)?
401        {
402            type Output = Matrix<R>;
403            fn $method(mut self, rhs: Self) -> Self::Output {
404                self.$method_assign(rhs);
405                self
406            }
407        }
408        impl<R> $imp<&Matrix<R>> for Matrix<R>
409        where
410            R: SemiRing,
411            $($($clauses)*)?
412        {
413            type Output = Matrix<R>;
414            fn $method(mut self, rhs: &Self) -> Self::Output {
415                self.$method_assign(rhs);
416                self
417            }
418        }
419        impl<R> $imp<Matrix<R>> for &Matrix<R>
420        where
421            R: SemiRing,
422            $($($clauses)*)?
423        {
424            type Output = Matrix<R>;
425            fn $method(self, mut rhs: Matrix<R>) -> Self::Output {
426                rhs.pairwise_assign(self, |a, b| *a = R::$method(b, a));
427                rhs
428            }
429        }
430        impl<R> $imp<&Matrix<R>> for &Matrix<R>
431        where
432            R: SemiRing,
433            $($($clauses)*)?
434        {
435            type Output = Matrix<R>;
436            fn $method(self, rhs: &Matrix<R>) -> Self::Output {
437                let mut this = self.clone();
438                this.$method_assign(rhs);
439                this
440            }
441        }
442    };
443}
444
445impl_matrix_pairwise_binop!(Add, add, AddAssign, add_assign);
446impl_matrix_pairwise_binop!(Sub, sub, SubAssign, sub_assign where [R::Additive: Invertible]);
447
448impl<R> Mul for Matrix<R>
449where
450    R: SemiRing,
451{
452    type Output = Matrix<R>;
453    fn mul(self, rhs: Self) -> Self::Output {
454        (&self).mul(&rhs)
455    }
456}
457impl<R> Mul<&Matrix<R>> for Matrix<R>
458where
459    R: SemiRing,
460{
461    type Output = Matrix<R>;
462    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
463        (&self).mul(rhs)
464    }
465}
466impl<R> Mul<Matrix<R>> for &Matrix<R>
467where
468    R: SemiRing,
469{
470    type Output = Matrix<R>;
471    fn mul(self, rhs: Matrix<R>) -> Self::Output {
472        self.mul(&rhs)
473    }
474}
475impl<R> Mul<&Matrix<R>> for &Matrix<R>
476where
477    R: SemiRing,
478{
479    type Output = Matrix<R>;
480    fn mul(self, rhs: &Matrix<R>) -> Self::Output {
481        assert_eq!(self.shape.1, rhs.shape.0);
482        let mut res = Matrix::zeros((self.shape.0, rhs.shape.1));
483        for i in 0..self.shape.0 {
484            for k in 0..self.shape.1 {
485                for j in 0..rhs.shape.1 {
486                    R::add_assign(&mut res[i][j], &R::mul(&self[i][k], &rhs[k][j]));
487                }
488            }
489        }
490        res
491    }
492}
493
494impl<R> MulAssign<&R::T> for Matrix<R>
495where
496    R: SemiRing,
497{
498    fn mul_assign(&mut self, rhs: &R::T) {
499        for i in 0..self.shape.0 {
500            for j in 0..self.shape.1 {
501                R::mul_assign(&mut self[(i, j)], rhs);
502            }
503        }
504    }

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§

Source §

impl<T> SemiRing for AddMulOperation<T>
where T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,

Source §

type T = T

Source §

type Additive = AdditiveOperation<T>

Source §

Trait SemiRing Copy item path

Required Associated Types§

type T: Clone

type Additive: AbelianMonoid<T = Self::T>

type Multiplicative: Monoid<T = Self::T>

Provided Methods§

fn zero() -> Self::T

fn is_zero(x: &Self::T) -> boolwhere Self::T: PartialEq,

fn one() -> Self::T

fn is_one(x: &Self::T) -> boolwhere Self::T: PartialEq,

fn add(x: &Self::T, y: &Self::T) -> Self::T

fn mul(x: &Self::T, y: &Self::T) -> Self::T

fn add_assign(x: &mut Self::T, y: &Self::T)

fn mul_assign(x: &mut Self::T, y: &Self::T)

Dyn Compatibility§

Implementors§

impl SemiRing for Gf2_63

type T = u64

type Additive = BitXorOperation<u64>

type Multiplicative = Gf2_63

impl SemiRing for Mersenne61

type T = u64

type Additive = Mersenne61Add

type Multiplicative = Mersenne61

impl<T> SemiRing for AddMulOperation<T>where T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,

type T = T

type Additive = AdditiveOperation<T>

type Multiplicative = MultiplicativeOperation<T>

Trait SemiRing

fn is_zero(x: &Self::T) -> bool
where Self::T: PartialEq,

fn is_one(x: &Self::T) -> bool
where Self::T: PartialEq,

impl<T> SemiRing for AddMulOperation<T>
where T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,