pub trait Ring: SemiRingwhere
Self::Additive: Invertible,{
// Provided methods
fn neg(x: &Self::T) -> Self::T { ... }
fn sub(x: &Self::T, y: &Self::T) -> Self::T { ... }
fn sub_assign(x: &mut Self::T, y: &Self::T) { ... }
}Provided Methods§
Sourcefn neg(x: &Self::T) -> Self::T
fn neg(x: &Self::T) -> Self::T
additive inverse: $-$
Examples found in repository?
crates/competitive/src/math/matrix.rs (line 227)
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 }More examples
crates/competitive/src/math/floor_sum.rs (line 319)
301pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
302 l: i64,
303 r: i64,
304 a: i64,
305 b: i64,
306 m: u64,
307) -> [[T; Y]; X]
308where
309 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
310 <AddMulOperation<T> as SemiRing>::Additive: Invertible,
311{
312 assert!(l <= r);
313 assert!(m > 0);
314
315 if a < 0 {
316 let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
317 for ans in ans.iter_mut().skip(1).step_by(2) {
318 for ans in ans.iter_mut() {
319 *ans = AddMulOperation::<T>::neg(ans);
320 }
321 }
322 return ans;
323 }
324
325 let add_x = l;
326 let n = (r - l) as u64;
327 let b = a * add_x + b;
328
329 let add_y = b.div_euclid(m as i64);
330 let b = b.rem_euclid(m as i64);
331 assert!(a >= 0);
332 assert!(b >= 0);
333 let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
334 FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
335 FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
336 n,
337 a as u64,
338 b as u64,
339 m,
340 );
341
342 let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
343 FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
344}crates/competitive/src/algorithm/automata_learning.rs (line 584)
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 sub(x: &Self::T, y: &Self::T) -> Self::T
fn sub(x: &Self::T, y: &Self::T) -> Self::T
additive right inversed operaion: $-$
Examples found in repository?
More examples
crates/competitive/src/math/quotient_array.rs (line 99)
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 }Sourcefn sub_assign(x: &mut Self::T, y: &Self::T)
fn sub_assign(x: &mut Self::T, y: &Self::T)
Examples found in repository?
crates/competitive/src/math/matrix.rs (line 202)
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 }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.