pub trait Field: Ring{
// 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 189)
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 }More examples
crates/competitive/src/algorithm/automata_learning.rs (line 576)
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 }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 45)
41 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
42 BitwisexorConvolve::<R::Additive, false>::hadamard_transform(&mut f);
43 let len = R::T::from(len);
44 for f in f.iter_mut() {
45 *f = R::div(f, &len);
46 }
47 f
48 }
49
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 }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.