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/bitwisexor_convolve.rs (line 73)
65 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
66 BitwisexorConvolve::<R::Additive, EXACT_DIVISION>::hadamard_transform(&mut f);
67 let len = R::T::from_length(len);
68 if EXACT_DIVISION {
69 for f in &mut f {
70 *f = R::div(f, &len);
71 }
72 } else if !f.is_empty() {
73 let inv_len = R::inv(&len);
74 for f in &mut f {
75 *f = R::mul(f, &inv_len);
76 }
77 }
78 f
79 }More examples
crates/competitive/src/math/matrix.rs (line 192)
158 fn eliminate<const DETERMINANT: bool>(&mut self) -> (usize, R::T) {
159 let (n, m) = self.shape;
160 let mut rank = 0;
161 let mut determinant = R::one();
162 let mut negative = false;
163 for first in (0..m).step_by(64) {
164 if rank == n {
165 break;
166 }
167 let end = (first + 64).min(m);
168 let start = rank;
169 let mut pivots = Vec::new();
170 let mut panel = vec![vec![R::zero(); end - first]; end - first];
171 for col in first..end {
172 if panel[col - first][..col - first]
173 .iter()
174 .any(|x| !R::is_zero(x))
175 {
176 for row in &mut self.data[rank..] {
177 let value =
178 R::dot_product(&row[first..col], &panel[col - first][..col - first]);
179 R::sub_assign(&mut row[col], &value);
180 }
181 }
182 let Some(pivot) = (rank..n).find(|&i| !R::is_zero(&self[i][col])) else {
183 continue;
184 };
185 if pivot != rank {
186 self.data.swap(rank, pivot);
187 negative = !negative;
188 }
189 if DETERMINANT {
190 R::mul_assign(&mut determinant, &self[rank][col]);
191 }
192 let inv = R::inv(&self[rank][col]);
193 let row = &mut self.data[rank];
194 for c in col + 1..end {
195 let value = R::dot_product(&row[first..col], &panel[c - first][..col - first]);
196 R::sub_assign(&mut row[c], &value);
197 panel[c - first][col - first] = row[c].clone();
198 }
199 for row in &mut self.data[rank + 1..] {
200 R::mul_assign(&mut row[col], &inv);
201 }
202 pivots.push(col);
203 rank += 1;
204 if rank == n {
205 break;
206 }
207 }
208 for i in start..if rank - start < 32 { n } else { rank } {
209 let (upper, lower) = self.data.split_at_mut(i);
210 let row = &mut lower[0];
211 for (j, &col) in pivots[..(i - start).min(pivots.len())].iter().enumerate() {
212 if R::is_zero(&row[col]) {
213 continue;
214 }
215 let factor = R::neg(&row[col]);
216 R::add_scaled_assign(&mut row[end..], &upper[start + j][end..], &factor);
217 }
218 }
219 if rank < n
220 && end < m
221 && rank - start >= 32
222 && self.data[rank..]
223 .iter()
224 .any(|row| pivots.iter().any(|&col| !R::is_zero(&row[col])))
225 {
226 let lower = Self::new_with((n - rank, rank - start), |i, j| {
227 R::neg(&self[rank + i][pivots[j]])
228 });
229 let upper = Self::new_with((rank - start, m - end), |i, j| {
230 self[start + i][end + j].clone()
231 });
232 let update = &lower * &upper;
233 for (row, update) in self.data[rank..].iter_mut().zip(update.data) {
234 for (x, y) in row[end..].iter_mut().zip(update) {
235 R::add_assign(x, &y);
236 }
237 }
238 }
239 for (i, &col) in pivots.iter().enumerate() {
240 for row in &mut self.data[start + i + 1..] {
241 row[col] = R::zero();
242 }
243 }
244 if DETERMINANT && rank < end {
245 return (rank, R::zero());
246 }
247 }
248 if DETERMINANT && negative {
249 determinant = R::neg(&determinant);
250 }
251 (rank, determinant)
252 }
253
254 /// f: (row, pivot_row, col)
255 pub fn row_reduction_with<F>(&mut self, normalize: bool, mut f: F)
256 where
257 F: FnMut(usize, usize, usize),
258 {
259 let (n, m) = self.shape;
260 let mut c = 0;
261 for r in 0..n {
262 loop {
263 if c >= m {
264 return;
265 }
266 if let Some(pivot) = (r..n).find(|&p| !R::is_zero(&self[p][c])) {
267 f(r, pivot, c);
268 self.data.swap(r, pivot);
269 break;
270 };
271 c += 1;
272 }
273 let d = R::inv(&self[r][c]);
274 if normalize {
275 for value in &mut self[r][c..m] {
276 R::mul_assign(value, &d);
277 }
278 }
279 for i in (0..n).filter(|&i| i != r) {
280 let mut e = self[i][c].clone();
281 if !normalize {
282 R::mul_assign(&mut e, &d);
283 }
284 for j in c..m {
285 let e = R::mul(&e, &self[r][j]);
286 R::sub_assign(&mut self[i][j], &e);
287 }
288 }
289 c += 1;
290 }
291 }
292
293 pub fn row_reduction(&mut self, normalize: bool) {
294 self.row_reduction_with(normalize, |_, _, _| {});
295 }
296
297 pub fn rank(&mut self) -> usize {
298 self.eliminate::<false>().0
299 }
300
301 pub fn determinant(&mut self) -> R::T {
302 assert_eq!(self.shape.0, self.shape.1);
303 self.eliminate::<true>().1
304 }
305
306 pub fn solve_system_of_linear_equations(
307 &self,
308 b: &[R::T],
309 ) -> Option<SystemOfLinearEquationsSolution<R>> {
310 assert_eq!(self.shape.0, b.len());
311 let m = self.shape.1;
312 let mut a = Self::new_with((self.shape.0, m + 1), |i, j| {
313 if j == m {
314 b[i].clone()
315 } else {
316 self[i][j].clone()
317 }
318 });
319 let rank = a.eliminate::<false>().0;
320 let mut pivots = Vec::with_capacity(rank);
321 let mut b = Vec::with_capacity(rank);
322 for row in &a.data[..rank] {
323 let c = row.iter().position(|x| !R::is_zero(x)).unwrap();
324 if c == m {
325 return None;
326 }
327 pivots.push(c);
328 b.push(row[m].clone());
329 }
330
331 let mut free = Vec::with_capacity(m - rank);
332 let mut pivot = 0;
333 for c in 0..m {
334 if pivot < rank && pivots[pivot] == c {
335 pivot += 1;
336 } else {
337 free.push(c);
338 }
339 }
340 let mut coefficients: Vec<Vec<_>> = (0..rank)
341 .map(|i| free.iter().map(|&c| a[i][c].clone()).collect())
342 .collect();
343 for k in (0..rank).rev() {
344 let c = pivots[k];
345 let inv = R::inv(&a[k][c]);
346 R::mul_assign(&mut b[k], &inv);
347 let pivot_b = b[k].clone();
348 let (upper, lower) = coefficients.split_at_mut(k);
349 let pivot_coefficients = &mut lower[0];
350 for x in pivot_coefficients.iter_mut() {
351 R::mul_assign(x, &inv);
352 }
353 for ((row, value), coefficients) in a.data[..k].iter_mut().zip(&mut b[..k]).zip(upper) {
354 if R::is_zero(&row[c]) {
355 continue;
356 }
357 let factor = row[c].clone();
358 row[c] = R::zero();
359 R::sub_assign(value, &R::mul(&factor, &pivot_b));
360 R::add_scaled_assign(coefficients, pivot_coefficients, &R::neg(&factor));
361 }
362 }
363
364 let mut particular = vec![R::zero(); m];
365 for i in 0..rank {
366 particular[pivots[i]] = b[i].clone();
367 }
368 let mut basis = Vec::with_capacity(free.len());
369 for (j, &c) in free.iter().enumerate() {
370 let mut vector = vec![R::zero(); m];
371 vector[c] = R::one();
372 for i in 0..rank {
373 vector[pivots[i]] = R::neg(&coefficients[i][j]);
374 }
375 basis.push(vector);
376 }
377 Some(SystemOfLinearEquationsSolution { particular, basis })
378 }
379
380 pub fn inverse(&self) -> Option<Matrix<R>> {
381 assert_eq!(self.shape.0, self.shape.1);
382 let n = self.shape.0;
383 if n >= 64 {
384 let m = n / 2;
385 let a = Self::new_with((m, m), |i, j| self[i][j].clone());
386 if let Some(mut ai) = a.inverse() {
387 let b = Self::new_with((m, n - m), |i, j| self[i][j + m].clone());
388 let c = Self::new_with((n - m, m), |i, j| self[i + m][j].clone());
389 let mut d = Self::new_with((n - m, n - m), |i, j| self[i + m][j + m].clone());
390 let u = &ai * &b;
391 let v = &c * &ai;
392 d -= &v * &b;
393 let di = d.inverse()?;
394 let r = &u * &di;
395 let t = &di * &v;
396 ai += &r * &v;
397 let mut inverse = Self::zeros((n, n));
398 for i in 0..m {
399 inverse[i][..m].clone_from_slice(&ai[i]);
400 for (x, y) in inverse[i][m..].iter_mut().zip(&r[i]) {
401 *x = R::neg(y);
402 }
403 }
404 for i in m..n {
405 for (x, y) in inverse[i][..m].iter_mut().zip(&t[i - m]) {
406 *x = R::neg(y);
407 }
408 inverse[i][m..].clone_from_slice(&di[i - m]);
409 }
410 return Some(inverse);
411 }
412 }
413 let mut a = self.clone();
414 let mut inverse = Self::eye((n, n));
415 let mut ranges: Vec<_> = (0..n).map(|i| (i, i + 1)).collect();
416 for r in 0..n {
417 let pivot = (r..n).find(|&i| !R::is_zero(&a[i][r]))?;
418 a.data.swap(r, pivot);
419 inverse.data.swap(r, pivot);
420 ranges.swap(r, pivot);
421
422 let d = R::inv(&a[r][r]);
423 for x in &mut a[r][r..] {
424 R::mul_assign(x, &d);
425 }
426 let (left, right) = ranges[r];
427 for x in &mut inverse[r][left..right] {
428 R::mul_assign(x, &d);
429 }
430
431 let (a_upper, a_lower) = a.data.split_at_mut(r + 1);
432 let pivot_a = &a_upper[r];
433 let (inverse_upper, inverse_lower) = inverse.data.split_at_mut(r + 1);
434 let pivot_inverse = &inverse_upper[r];
435 let (ranges_upper, ranges_lower) = ranges.split_at_mut(r + 1);
436 let (left, right) = ranges_upper[r];
437 for ((a, inverse), range) in a_lower.iter_mut().zip(inverse_lower).zip(ranges_lower) {
438 if R::is_zero(&a[r]) {
439 continue;
440 }
441 let e = a[r].clone();
442 a[r] = R::zero();
443 R::add_scaled_assign(&mut a[(r + 1)..], &pivot_a[(r + 1)..], &R::neg(&e));
444 R::add_scaled_assign(
445 &mut inverse[left..right],
446 &pivot_inverse[left..right],
447 &R::neg(&e),
448 );
449 range.0 = range.0.min(left);
450 range.1 = range.1.max(right);
451 }
452 }
453 for r in (0..n).rev() {
454 let (left, right) = ranges[r];
455 let (inverse_upper, inverse_lower) = inverse.data.split_at_mut(r);
456 let pivot_inverse = &inverse_lower[0];
457 let (ranges_upper, _) = ranges.split_at_mut(r);
458 for ((a, inverse), range) in a.data[..r].iter_mut().zip(inverse_upper).zip(ranges_upper)
459 {
460 if R::is_zero(&a[r]) {
461 continue;
462 }
463 let e = a[r].clone();
464 a[r] = R::zero();
465 R::add_scaled_assign(
466 &mut inverse[left..right],
467 &pivot_inverse[left..right],
468 &R::neg(&e),
469 );
470 range.0 = range.0.min(left);
471 range.1 = range.1.max(right);
472 }
473 }
474 Some(inverse)
475 }
476
477 pub fn characteristic_polynomial(&mut self) -> Vec<R::T> {
478 let n = self.shape.0;
479 if n == 0 {
480 return vec![R::one()];
481 }
482 assert!(self.data.iter().all(|a| a.len() == n));
483 for j in 0..(n - 1) {
484 if let Some(x) = ((j + 1)..n).find(|&x| !R::is_zero(&self[x][j])) {
485 self.data.swap(j + 1, x);
486 self.data.iter_mut().for_each(|a| a.swap(j + 1, x));
487 let inv = R::inv(&self[j + 1][j]);
488 let mut v = vec![];
489 let src = std::mem::take(&mut self[j + 1]);
490 for a in self.data[(j + 2)..].iter_mut() {
491 let mul = R::mul(&a[j], &inv);
492 R::add_scaled_assign(&mut a[j..], &src[j..], &R::neg(&mul));
493 v.push(mul);
494 }
495 self[j + 1] = src;
496 for a in self.data.iter_mut() {
497 let v = R::dot_product(&a[(j + 2)..], &v);
498 R::add_assign(&mut a[j + 1], &v);
499 }
500 }
501 }
502 // dp[k][j - k] stores [x^k] det(xI - A[..j, ..j]).
503 let mut dp: Vec<Vec<R::T>> = (0..=n).map(|i| Vec::with_capacity(n + 1 - i)).collect();
504 dp[0].push(R::one());
505 for i in 0..n {
506 let mut c = vec![R::zero(); i + 1];
507 c[i] = R::neg(&self[i][i]);
508 let mut mul = R::one();
509 for j in (0..i).rev() {
510 mul = R::mul(&mul, &self[j + 1][j]);
511 c[j] = R::neg(&R::mul(&mul, &self[j][i]));
512 }
513 for k in (0..=i).rev() {
514 let mut value = R::dot_product(&dp[k], &c[k..]);
515 if k > 0 {
516 R::add_assign(&mut value, dp[k - 1].last().unwrap());
517 }
518 dp[k].push(value);
519 }
520 dp[i + 1].push(R::one());
521 }
522 dp.into_iter().map(|mut c| c.pop().unwrap()).collect()
523 }crates/competitive/src/math/black_box_matrix.rs (line 176)
97 pub fn determinant(&self) -> R::T {
98 assert_eq!(self.shape.0, self.shape.1);
99 let n = self.shape.0;
100 let mut columns = vec![Vec::<(usize, R::T)>::new(); n];
101 for &(i, j, ref value) in &self.nonzero {
102 columns[j].push((i, value.clone()));
103 }
104 let mut degrees = vec![0; n];
105 for column in &mut columns {
106 column.sort_unstable_by_key(|&(i, _)| i);
107 let mut merged: Vec<(usize, R::T)> = Vec::with_capacity(column.len());
108 for (i, value) in column.drain(..) {
109 if let Some((_, x)) = merged.last_mut().filter(|(last, _)| *last == i) {
110 R::add_assign(x, &value);
111 } else {
112 merged.push((i, value));
113 }
114 }
115 merged.retain(|(i, value)| {
116 if R::is_zero(value) {
117 false
118 } else {
119 degrees[*i] += 1;
120 true
121 }
122 });
123 *column = merged;
124 }
125 let mut order: Vec<_> = (0..n).collect();
126 order.sort_unstable_by_key(|&j| columns[j].len());
127 let mut lower: Vec<Vec<(usize, R::T)>> = Vec::with_capacity(n);
128 let mut pivots: Vec<Option<usize>> = vec![None; n];
129 let mut x = vec![R::zero(); n];
130 let mut seen = vec![0; n];
131 let mut stack = Vec::new();
132 let mut support = Vec::new();
133 let mut determinant = R::one();
134 for (k, &j) in order.iter().enumerate() {
135 support.clear();
136 for &(i, _) in &columns[j] {
137 if seen[i] == k + 1 {
138 continue;
139 }
140 seen[i] = k + 1;
141 x[i] = R::zero();
142 stack.push((i, 0));
143 while let Some((i, next)) = stack.last_mut() {
144 if let Some(pivot) = pivots[*i]
145 && *next < lower[pivot].len()
146 {
147 let row = lower[pivot][*next].0;
148 *next += 1;
149 if seen[row] != k + 1 {
150 seen[row] = k + 1;
151 x[row] = R::zero();
152 stack.push((row, 0));
153 }
154 continue;
155 }
156 support.push(*i);
157 stack.pop();
158 }
159 }
160 for &(i, ref value) in &columns[j] {
161 x[i] = value.clone();
162 }
163 let mut pivot = None;
164 for &i in support.iter().rev() {
165 if let Some(p) = pivots[i] {
166 let factor = R::neg(&x[i]);
167 for &(row, ref value) in &lower[p] {
168 R::add_assign(&mut x[row], &R::mul(&factor, value));
169 }
170 } else if !R::is_zero(&x[i]) && pivot.is_none_or(|p| degrees[i] < degrees[p]) {
171 pivot = Some(i);
172 }
173 }
174 let Some(pivot) = pivot else { return R::zero() };
175 R::mul_assign(&mut determinant, &x[pivot]);
176 let inv = R::inv(&x[pivot]);
177 pivots[pivot] = Some(k);
178 lower.push(
179 support
180 .iter()
181 .filter(|&&i| pivots[i].is_none() && !R::is_zero(&x[i]))
182 .map(|&i| (i, R::mul(&x[i], &inv)))
183 .collect(),
184 );
185 }
186 for mut permutation in [order, pivots.into_iter().map(Option::unwrap).collect()] {
187 for i in 0..n {
188 while permutation[i] != i {
189 let j = permutation[i];
190 permutation.swap(i, j);
191 determinant = R::neg(&determinant);
192 }
193 }
194 }
195 determinant
196 }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 70)
65 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
66 BitwisexorConvolve::<R::Additive, EXACT_DIVISION>::hadamard_transform(&mut f);
67 let len = R::T::from_length(len);
68 if EXACT_DIVISION {
69 for f in &mut f {
70 *f = R::div(f, &len);
71 }
72 } else if !f.is_empty() {
73 let inv_len = R::inv(&len);
74 for f in &mut f {
75 *f = R::mul(f, &inv_len);
76 }
77 }
78 f
79 }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".