pub trait Field: Ring<Multiplicative: Invertible> {
// Provided methods
fn inv(x: &Self::T) -> Self::T { ... }
fn div(x: &Self::T, y: &Self::T) -> Self::T { ... }
fn div_assign(x: &mut Self::T, y: &Self::T) { ... }
}Provided Methods§
Sourcefn inv(x: &Self::T) -> Self::T
fn inv(x: &Self::T) -> Self::T
multiplicative inverse: $-$
Examples found in repository?
crates/competitive/src/math/matrix.rs (line 177)
159 pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
160 where
161 F: FnMut(usize, usize, usize),
162 {
163 let (n, m) = self.shape;
164 let mut c = 0;
165 for r in 0..n {
166 loop {
167 if c >= m {
168 return;
169 }
170 if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
171 f(r, pivot, c);
172 self.data.swap(r, pivot);
173 break;
174 };
175 c += 1;
176 }
177 let d = R::inv(&self[r][c]);
178 if normalize {
179 for j in c..m {
180 R::mul_assign(&mut self[r][j], &d);
181 }
182 }
183 for i in (0..n).filter(|&i| i != r) {
184 let mut e = self[i][c].clone();
185 if !normalize {
186 R::mul_assign(&mut e, &d);
187 }
188 for j in c..m {
189 let e = R::mul(&e, &self[r][j]);
190 R::sub_assign(&mut self[i][j], &e);
191 }
192 }
193 c += 1;
194 }
195 }
196
197 pub fn row_reduction(&mut self, normalize: bool) {
198 self.row_reduction_with(normalize, |_, _, _| {});
199 }
200
201 pub fn rank(&mut self) -> usize {
202 let n = self.shape.0;
203 self.row_reduction(false);
204 (0..n)
205 .filter(|&i| !self.data[i].iter().all(|x| R::is_zero(x)))
206 .count()
207 }
208
209 pub fn determinant(&mut self) -> R::T {
210 assert_eq!(self.shape.0, self.shape.1);
211 let mut neg = false;
212 self.row_reduction_with(false, |r, p, _| neg ^= r != p);
213 let mut d = R::one();
214 if neg {
215 d = R::neg(&d);
216 }
217 for i in 0..self.shape.0 {
218 R::mul_assign(&mut d, &self[i][i]);
219 }
220 d
221 }
222
223 pub fn solve_system_of_linear_equations(
224 &self,
225 b: &[R::T],
226 ) -> Option<SystemOfLinearEquationsSolution<R>> {
227 assert_eq!(self.shape.0, b.len());
228 let (n, m) = self.shape;
229 let mut c = Matrix::<R>::zeros((n, m + 1));
230 for i in 0..n {
231 c[i][..m].clone_from_slice(&self[i]);
232 c[i][m] = b[i].clone();
233 }
234 let mut reduced = vec![!0; m + 1];
235 c.row_reduction_with(true, |r, _, c| reduced[c] = r);
236 if reduced[m] != !0 {
237 return None;
238 }
239 let mut particular = vec![R::zero(); m];
240 let mut basis = vec![];
241 for j in 0..m {
242 if reduced[j] != !0 {
243 particular[j] = c[reduced[j]][m].clone();
244 } else {
245 let mut v = vec![R::zero(); m];
246 v[j] = R::one();
247 for i in 0..m {
248 if reduced[i] != !0 {
249 R::sub_assign(&mut v[i], &c[reduced[i]][j]);
250 }
251 }
252 basis.push(v);
253 }
254 }
255 Some(SystemOfLinearEquationsSolution { particular, basis })
256 }
257
258 pub fn inverse(&self) -> Option<Matrix<R>> {
259 assert_eq!(self.shape.0, self.shape.1);
260 let n = self.shape.0;
261 let mut c = Matrix::<R>::zeros((n, n * 2));
262 for i in 0..n {
263 c[i][..n].clone_from_slice(&self[i]);
264 c[i][n + i] = R::one();
265 }
266 c.row_reduction(true);
267 if (0..n).any(|i| R::is_zero(&c[i][i])) {
268 None
269 } else {
270 Some(Self::from_vec(
271 c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
272 ))
273 }
274 }
275
276 pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
277 let n = self.shape.0;
278 if n == 0 {
279 return vec![R::one()];
280 }
281 assert!(self.data.iter().all(|a| a.len() == n));
282 for j in 0..(n - 1) {
283 if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
284 self.data.swap(j + 1, x);
285 self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
286 let inv = R::inv(&self[j + 1][j]);
287 let mut v = vec![];
288 let src = std::mem::take(&mut self[j + 1]);
289 for a in self.data[(j + 2)..].iter_mut() {
290 let mul = R::mul(&a[j], &inv);
291 for (a, src) in a[j..].iter_mut().zip(src[j..].iter()) {
292 R::sub_assign(a, &R::mul(&mul, src));
293 }
294 v.push(mul);
295 }
296 self[j + 1] = src;
297 for a in self.data.iter_mut() {
298 let v = a[(j + 2)..]
299 .iter()
300 .zip(v.iter())
301 .fold(R::zero(), |s, a| R::add(&s, &R::mul(a.0, a.1)));
302 R::add_assign(&mut a[j + 1], &v);
303 }
304 }
305 }
306 let mut dp = vec![vec![R::one()]];
307 for i in 0..n {
308 let mut next = vec![R::zero(); i + 2];
309 for (j, dp) in dp[i].iter().enumerate() {
310 R::sub_assign(&mut next[j], &R::mul(dp, &self[i][i]));
311 R::add_assign(&mut next[j + 1], dp);
312 }
313 let mut mul = R::one();
314 for j in (0..i).rev() {
315 mul = R::mul(&mul, &self[j + 1][j]);
316 let c = R::mul(&mul, &self[j][i]);
317 for (next, dp) in next.iter_mut().zip(dp[j].iter()) {
318 R::sub_assign(next, &R::mul(&c, dp));
319 }
320 }
321 dp.push(next);
322 }
323 dp.pop().unwrap()
324 }More examples
crates/competitive/src/algorithm/automata_learning.rs (line 554)
523 pub fn train_sample(&mut self, sample: &[usize]) -> bool {
524 let Some((prefix, suffix)) = self.split_sample(sample) else {
525 return false;
526 };
527 self.prefixes.push(prefix);
528 self.suffixes.push(suffix);
529 let n = self.inv_h.shape.0;
530 let prefix = &self.prefixes[n];
531 let suffix = &self.suffixes[n];
532 let u = Matrix::<F>::new_with((n, 1), |i, _| {
533 self.automaton.behavior(
534 self.prefixes[i]
535 .iter()
536 .cloned()
537 .chain(suffix.iter().cloned()),
538 )
539 });
540 let v = Matrix::<F>::new_with((1, n), |_, j| {
541 self.automaton.behavior(
542 prefix
543 .iter()
544 .cloned()
545 .chain(self.suffixes[j].iter().cloned()),
546 )
547 });
548 let w = Matrix::<F>::new_with((1, 1), |_, _| {
549 self.automaton
550 .behavior(prefix.iter().cloned().chain(suffix.iter().cloned()))
551 });
552 let t = &self.inv_h * &u;
553 let s = &v * &self.inv_h;
554 let d = F::inv(&(&w - &(&v * &t))[0][0]);
555 let dh = &t * &s;
556 for i in 0..n {
557 for j in 0..n {
558 F::add_assign(&mut self.inv_h[i][j], &F::mul(&dh[i][j], &d));
559 }
560 }
561 self.inv_h
562 .add_col_with(|i, _| F::neg(&F::mul(&t[i][0], &d)));
563 self.inv_h.add_row_with(|_, j| {
564 if j != n {
565 F::neg(&F::mul(&s[0][j], &d))
566 } else {
567 d.clone()
568 }
569 });
570
571 for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
572 let b = &(&self.nh[x] * &t) * &s;
573 for i in 0..n {
574 for j in 0..n {
575 F::add_assign(&mut transition[i][j], &F::mul(&b[i][j], &d));
576 }
577 }
578 }
579 for (x, nh) in self.nh.iter_mut().enumerate() {
580 nh.add_col_with(|i, j| {
581 self.automaton.behavior(
582 self.prefixes[i]
583 .iter()
584 .cloned()
585 .chain([x])
586 .chain(self.suffixes[j].iter().cloned()),
587 )
588 });
589 nh.add_row_with(|i, j| {
590 self.automaton.behavior(
591 self.prefixes[i]
592 .iter()
593 .cloned()
594 .chain([x])
595 .chain(self.suffixes[j].iter().cloned()),
596 )
597 });
598 }
599 self.wfa
600 .initial_weights
601 .add_col_with(|_, _| if n == 0 { F::one() } else { F::zero() });
602 self.wfa
603 .final_weights
604 .add_row_with(|_, _| self.automaton.behavior(prefix.iter().cloned()));
605 for (x, transition) in self.wfa.transitions.iter_mut().enumerate() {
606 transition.add_col_with(|_, _| F::zero());
607 transition.add_row_with(|_, _| F::zero());
608 for i in 0..=n {
609 for j in 0..=n {
610 if i == n || j == n {
611 for k in 0..=n {
612 if i != n && j != n && k != n {
613 continue;
614 }
615 F::add_assign(
616 &mut transition[i][k],
617 &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
618 );
619 }
620 } else {
621 let k = n;
622 F::add_assign(
623 &mut transition[i][k],
624 &F::mul(&self.nh[x][i][j], &self.inv_h[j][k]),
625 );
626 }
627 }
628 }
629 }
630 true
631 }Sourcefn div(x: &Self::T, y: &Self::T) -> Self::T
fn div(x: &Self::T, y: &Self::T) -> Self::T
multiplicative right inversed operaion: $-$
Examples found in repository?
crates/competitive/src/math/bitwisexor_convolve.rs (line 41)
37 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
38 BitwisexorConvolve::<R::Additive, false>::hadamard_transform(&mut f);
39 let len = R::T::from(len);
40 for f in f.iter_mut() {
41 *f = R::div(f, &len);
42 }
43 f
44 }
45
46 fn multiply(f: &mut Self::F, g: &Self::F) {
47 for (f, g) in f.iter_mut().zip(g) {
48 *f = R::mul(f, g);
49 }
50 }
51
52 fn convolve(a: Self::T, b: Self::T) -> Self::T {
53 assert_eq!(a.len(), b.len());
54 let len = a.len();
55 let same = a == b;
56 let mut a = Self::transform(a, len);
57 if same {
58 for a in a.iter_mut() {
59 *a = R::mul(a, a);
60 }
61 } else {
62 let b = Self::transform(b, len);
63 Self::multiply(&mut a, &b);
64 }
65 Self::inverse_transform(a, len)
66 }
67}
68
69impl<R> ConvolveSteps for BitwisexorConvolve<R, true>
70where
71 R: Field<T: PartialEq + TryFrom<usize>, Additive: Invertible, Multiplicative: Invertible>,
72 <R::T as TryFrom<usize>>::Error: Debug,
73{
74 type T = Vec<R::T>;
75 type F = Vec<R::T>;
76
77 fn length(t: &Self::T) -> usize {
78 t.len()
79 }
80
81 fn transform(mut t: Self::T, _len: usize) -> Self::F {
82 BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut t);
83 t
84 }
85
86 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
87 BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut f);
88 let len = R::T::try_from(len).unwrap();
89 for f in f.iter_mut() {
90 *f = R::div(f, &len);
91 }
92 f
93 }fn div_assign(x: &mut Self::T, y: &Self::T)
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.