pub trait Zero: Sized {
// Required method
fn zero() -> Self;
// Provided methods
fn is_zero(&self) -> bool
where Self: PartialEq { ... }
fn set_zero(&mut self) { ... }
}Required Methods§
Provided Methods§
Sourcefn is_zero(&self) -> boolwhere
Self: PartialEq,
fn is_zero(&self) -> boolwhere
Self: PartialEq,
Examples found in repository?
crates/competitive/src/num/integer.rs (line 92)
91 fn lcm(self, other: Self) -> Self {
92 if self.is_zero() && other.is_zero() {
93 Self::zero()
94 } else {
95 self / self.gcd(other) * other
96 }
97 }
98 fn mod_inv(self, modulo: Self) -> Self {
99 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
100 let extgcd = self.signed().extgcd(modulo.signed());
101 debug_assert!(extgcd.g.is_one(), "not coprime");
102 extgcd.x.rem_euclid(modulo.signed()).unsigned()
103 }
104 fn mod_add(self, rhs: Self, modulo: Self) -> Self;
105 fn mod_sub(self, rhs: Self, modulo: Self) -> Self;
106 fn mod_mul(self, rhs: Self, modulo: Self) -> Self;
107 fn mod_neg(self, modulo: Self) -> Self {
108 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
109 debug_assert!(self < modulo, "self must be less than modulo");
110 if self.is_zero() {
111 Self::zero()
112 } else {
113 modulo - self
114 }
115 }
116}
117
118/// Trait for signed integer operations.
119pub trait Signed: IntBase + Neg<Output = Self> {
120 type Unsigned: Unsigned<Signed = Self>;
121 fn unsigned(self) -> Self::Unsigned;
122 fn abs(self) -> Self;
123 fn abs_diff(self, other: Self) -> Self::Unsigned;
124 fn is_negative(self) -> bool;
125 fn is_positive(self) -> bool;
126 fn signum(self) -> Self;
127 fn extgcd(self, other: Self) -> ExtendedGcd<Self> {
128 let (mut a, mut b) = (self, other);
129 let (mut u, mut v, mut x, mut y) = (Self::one(), Self::zero(), Self::zero(), Self::one());
130 while !a.is_zero() {
131 let k = b / a;
132 x -= k * u;
133 y -= k * v;
134 b -= k * a;
135 std::mem::swap(&mut x, &mut u);
136 std::mem::swap(&mut y, &mut v);
137 std::mem::swap(&mut b, &mut a);
138 }
139 if b.is_negative() {
140 b = -b;
141 x = -x;
142 y = -y;
143 }
144 ExtendedGcd {
145 g: b.unsigned(),
146 x,
147 y,
148 }
149 }More examples
crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 87)
84 pub fn trim_tail_zeros(&mut self) {
85 let mut len = self.length();
86 while len > 0 {
87 if self.data[len - 1].is_zero() {
88 len -= 1;
89 } else {
90 break;
91 }
92 }
93 self.truncate(len);
94 }
95}
96
97impl<T, C> Zero for FormalPowerSeries<T, C>
98where
99 T: PartialEq,
100{
101 fn zero() -> Self {
102 Self::from_vec(Vec::new())
103 }
104}
105impl<T, C> One for FormalPowerSeries<T, C>
106where
107 T: PartialEq + One,
108{
109 fn one() -> Self {
110 Self::from(T::one())
111 }
112}
113
114impl<T, C> IntoIterator for FormalPowerSeries<T, C> {
115 type Item = T;
116 type IntoIter = std::vec::IntoIter<T>;
117 fn into_iter(self) -> Self::IntoIter {
118 self.data.into_iter()
119 }
120}
121impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C> {
122 type Item = &'a T;
123 type IntoIter = Iter<'a, T>;
124 fn into_iter(self) -> Self::IntoIter {
125 self.data.iter()
126 }
127}
128impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C> {
129 type Item = &'a mut T;
130 type IntoIter = IterMut<'a, T>;
131 fn into_iter(self) -> Self::IntoIter {
132 self.data.iter_mut()
133 }
134}
135
136impl<T, C> FromIterator<T> for FormalPowerSeries<T, C> {
137 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
138 Self::from_vec(iter.into_iter().collect())
139 }
140}
141
142impl<T, C> Index<usize> for FormalPowerSeries<T, C> {
143 type Output = T;
144 fn index(&self, index: usize) -> &Self::Output {
145 &self.data[index]
146 }
147}
148impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C> {
149 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
150 &mut self.data[index]
151 }
152}
153
154impl<T, C> From<T> for FormalPowerSeries<T, C> {
155 fn from(x: T) -> Self {
156 once(x).collect()
157 }
158}
159impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C> {
160 fn from(data: Vec<T>) -> Self {
161 Self::from_vec(data)
162 }
163}
164
165impl<T, C> FormalPowerSeries<T, C>
166where
167 T: FormalPowerSeriesCoefficient,
168{
169 pub fn prefix_ref(&self, deg: usize) -> Self {
170 if deg < self.length() {
171 Self::from_vec(self.data[..deg].to_vec())
172 } else {
173 self.clone()
174 }
175 }
176 pub fn prefix(mut self, deg: usize) -> Self {
177 self.data.truncate(deg);
178 self
179 }
180 pub fn even(mut self) -> Self {
181 let mut keep = false;
182 self.data.retain(|_| {
183 keep = !keep;
184 keep
185 });
186 self
187 }
188 pub fn odd(mut self) -> Self {
189 let mut keep = true;
190 self.data.retain(|_| {
191 keep = !keep;
192 keep
193 });
194 self
195 }
196 pub fn diff(mut self) -> Self {
197 let mut c = T::one();
198 for x in self.iter_mut().skip(1) {
199 *x *= &c;
200 c += T::one();
201 }
202 if self.length() > 0 {
203 self.data.remove(0);
204 }
205 self
206 }
207 pub fn integral(mut self) -> Self {
208 let n = self.length();
209 self.data.insert(0, Zero::zero());
210 let mut fact = Vec::with_capacity(n + 1);
211 let mut c = T::one();
212 fact.push(c.clone());
213 for _ in 1..n {
214 fact.push(fact.last().cloned().unwrap() * c.clone());
215 c += T::one();
216 }
217 let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
218 for x in self.iter_mut().skip(1).rev() {
219 *x *= invf.clone() * fact.pop().unwrap();
220 invf *= c.clone();
221 c -= T::one();
222 }
223 self
224 }
225 pub fn parity_inversion(mut self) -> Self {
226 self.iter_mut()
227 .skip(1)
228 .step_by(2)
229 .for_each(|x| *x = -x.clone());
230 self
231 }
232 pub fn eval(&self, x: T) -> T {
233 let mut base = T::one();
234 let mut res = T::zero();
235 for a in self.iter() {
236 res += base.clone() * a.clone();
237 base *= x.clone();
238 }
239 res
240 }
241}
242
243impl<T, C> FormalPowerSeries<T, C>
244where
245 T: FormalPowerSeriesCoefficient,
246 C: ConvolveSteps<T = Vec<T>>,
247{
248 pub fn inv(&self, deg: usize) -> Self {
249 debug_assert!(!self[0].is_zero());
250 if self.data.iter().filter(|x| !x.is_zero()).count()
251 <= deg.next_power_of_two().trailing_zeros() as usize * 6
252 {
253 let pos: Vec<_> = self
254 .data
255 .iter()
256 .enumerate()
257 .skip(1)
258 .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
259 .collect();
260 let mut f = Self::zeros(deg);
261 f[0] = T::one() / self[0].clone();
262 for i in 1..deg {
263 let mut tot = T::zero();
264 for &j in &pos {
265 if j > i {
266 break;
267 }
268 tot += self[j].clone() * &f[i - j];
269 }
270 f[i] = -tot * &f[0];
271 }
272 return f;
273 }
274 let mut f = Self::from(T::one() / self[0].clone());
275 let mut i = 1;
276 while i < deg {
277 let g = self.prefix_ref((i * 2).min(deg));
278 let h = f.clone();
279 let mut g = C::transform(g.data, 2 * i);
280 let h = C::transform(h.data, 2 * i);
281 C::multiply(&mut g, &h);
282 let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
283 g >>= i;
284 let mut g = C::transform(g.data, 2 * i);
285 C::multiply(&mut g, &h);
286 let g = Self::from_vec(C::inverse_transform(g, 2 * i));
287 f.data.extend((-g).into_iter().take(i));
288 i *= 2;
289 }
290 f.truncate(deg);
291 f
292 }
293 pub fn exp(&self, deg: usize) -> Self {
294 debug_assert!(self[0].is_zero());
295 if self.data.iter().filter(|x| !x.is_zero()).count()
296 <= deg.next_power_of_two().trailing_zeros() as usize * 16
297 {
298 let diff = self.clone().diff();
299 let pos: Vec<_> = diff
300 .data
301 .iter()
302 .enumerate()
303 .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304 .collect();
305 let mf = T::memorized_factorial(deg);
306 let mut f = Self::zeros(deg);
307 f[0] = T::one();
308 for i in 1..deg {
309 let mut tot = T::zero();
310 for &j in &pos {
311 if j > i - 1 {
312 break;
313 }
314 tot += f[i - 1 - j].clone() * &diff[j];
315 }
316 f[i] = tot * T::memorized_inv(&mf, i);
317 }
318 return f;
319 }
320 let mut f = Self::one();
321 let mut i = 1;
322 while i < deg {
323 let mut g = -f.log(i * 2);
324 g[0] += T::one();
325 for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326 *g += x.clone();
327 }
328 f = (f * g).prefix(i * 2);
329 i *= 2;
330 }
331 f.prefix(deg)
332 }
333 pub fn log(&self, deg: usize) -> Self {
334 (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335 }
336 pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337 if rhs == 0 {
338 return Self::from_vec(
339 once(T::one())
340 .chain(repeat_with(T::zero))
341 .take(deg)
342 .collect(),
343 );
344 }
345 if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346 if k >= deg.div_ceil(rhs) {
347 Self::zeros(deg)
348 } else {
349 let deg = deg - k * rhs;
350 let x0 = self[k].clone();
351 let mut f = (self >> k) / &x0;
352 if f.data.iter().filter(|x| !x.is_zero()).count()
353 <= deg.next_power_of_two().trailing_zeros() as usize * 12
354 {
355 f = f.pow_sparse1(T::from(rhs), deg);
356 } else {
357 f = (f.log(deg) * &T::from(rhs)).exp(deg);
358 }
359 f *= x0.pow(rhs);
360 f <<= k * rhs;
361 f
362 }
363 } else {
364 Self::zeros(deg)
365 }
366 }
367 fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368 debug_assert!(!self[0].is_zero());
369 let pos: Vec<_> = self
370 .data
371 .iter()
372 .enumerate()
373 .skip(1)
374 .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375 .collect();
376 let mf = T::memorized_factorial(deg);
377 let mut f = Self::zeros(deg);
378 f[0] = T::one();
379 for i in 1..deg {
380 let mut tot = T::zero();
381 for &j in &pos {
382 if j > i {
383 break;
384 }
385 tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386 }
387 f[i] = tot * T::memorized_inv(&mf, i);
388 }
389 f
390 }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395 T: FormalPowerSeriesCoefficientSqrt,
396 C: ConvolveSteps<T = Vec<T>>,
397{
398 pub fn sqrt(&self, deg: usize) -> Option<Self> {
399 if self[0].is_zero() {
400 if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401 if k % 2 != 0 {
402 return None;
403 } else if deg > k / 2 {
404 return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405 }
406 }
407 } else {
408 let s = self[0].sqrt_coefficient()?;
409 if self.data.iter().filter(|x| !x.is_zero()).count()
410 <= deg.next_power_of_two().trailing_zeros() as usize * 4
411 {
412 let t = self[0].clone();
413 let mut f = self / t;
414 f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415 f *= s;
416 return Some(f);
417 }
418
419 let mut f = Self::from(s);
420 let inv2 = T::one() / (T::one() + T::one());
421 let mut i = 1;
422 while i < deg {
423 f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424 i *= 2;
425 }
426 f.truncate(deg);
427 return Some(f);
428 }
429 Some(Self::zeros(deg))
430 }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435 T: FormalPowerSeriesCoefficient,
436 C: ConvolveSteps<T = Vec<T>>,
437{
438 pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439 where
440 F: FnMut(usize) -> T,
441 {
442 let n = self.length();
443 let mut f = Self::zeros(n);
444 for i in 1..n {
445 if !self[i].is_zero() {
446 for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447 if j & 1 != 0 {
448 f[d] += self[i].clone() * &inverse(j);
449 } else {
450 f[d] -= self[i].clone() * &inverse(j);
451 }
452 }
453 }
454 }
455 f.exp(deg)
456 }
457 pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458 where
459 F: FnMut(usize) -> T,
460 {
461 let n = self.length();
462 let mut f = Self::zeros(n);
463 for i in 1..n {
464 if !self[i].is_zero() {
465 for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466 f[d] += self[i].clone() * &inverse(j);
467 }
468 }
469 }
470 f.exp(deg)
471 }crates/competitive/src/algorithm/bitdp.rs (line 73)
71 fn next(&mut self) -> Option<Self::Item> {
72 if let Some(cur) = self.cur {
73 self.cur = if cur.is_zero() {
74 None
75 } else {
76 Some((cur - T::one()) & self.mask)
77 };
78 Some(cur)
79 } else {
80 None
81 }
82 }Additional examples can be found in:
- crates/competitive/src/num/double_double.rs
- crates/competitive/src/algorithm/stern_brocot_tree.rs
- crates/competitive/src/math/garner.rs
- crates/competitive/src/math/black_box_matrix.rs
- crates/competitive/src/math/linear_diophantine.rs
- crates/competitive/src/string/wildcard_pattern_matching.rs
- crates/competitive/src/math/lagrange_interpolation.rs
- crates/competitive/src/algebra/lazy_map.rs
- crates/competitive/src/math/berlekamp_massey.rs
- crates/competitive/src/math/mint_matrix.rs
- crates/competitive/src/graph/network_simplex.rs
fn set_zero(&mut self)
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.