Trait Zero

Source

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§

Source

fn zero() -> Self

Provided Methods§

Source

fn is_zero(&self) -> bool
where Self: PartialEq,

Examples found in repository ?

crates/competitive/src/num/integer.rs (line 84)

83    fn lcm(self, other: Self) -> Self {
84        if self.is_zero() && other.is_zero() {
85            Self::zero()
86        } else {
87            self / self.gcd(other) * other
88        }
89    }
90    fn mod_inv(self, modulo: Self) -> Self {
91        assert!(
92            !self.is_zero(),
93            "attempt to inverse zero with modulo {}",
94            modulo
95        );
96        let extgcd = self.signed().extgcd(modulo.signed());
97        assert!(
98            extgcd.g.is_one(),
99            "there is no inverse {} modulo {}",
100            self,
101            modulo
102        );
103        extgcd.x.rem_euclid(modulo.signed()).unsigned()
104    }
105    fn mod_add(self, rhs: Self, modulo: Self) -> Self;
106    fn mod_sub(self, rhs: Self, modulo: Self) -> Self;
107    fn mod_mul(self, rhs: Self, modulo: Self) -> Self;
108    fn mod_neg(self, modulo: Self) -> Self {
109        debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
110        debug_assert!(self < modulo, "self must be less than modulo");
111        if self.is_zero() {
112            Self::zero()
113        } else {
114            modulo - self
115        }
116    }
117}
118
119/// Trait for signed integer operations.
120pub trait Signed: IntBase + Neg<Output = Self> {
121    type Unsigned: Unsigned<Signed = Self>;
122    fn unsigned(self) -> Self::Unsigned;
123    fn abs(self) -> Self;
124    fn abs_diff(self, other: Self) -> Self::Unsigned;
125    fn is_negative(self) -> bool;
126    fn is_positive(self) -> bool;
127    fn signum(self) -> Self;
128    fn extgcd(self, other: Self) -> ExtendedGcd<Self> {
129        let (mut a, mut b) = (self, other);
130        let (mut u, mut v, mut x, mut y) = (Self::one(), Self::zero(), Self::zero(), Self::one());
131        while !a.is_zero() {
132            let k = b / a;
133            x -= k * u;
134            y -= k * v;
135            b -= k * a;
136            std::mem::swap(&mut x, &mut u);
137            std::mem::swap(&mut y, &mut v);
138            std::mem::swap(&mut b, &mut a);
139        }
140        if b.is_negative() {
141            b = -b;
142            x = -x;
143            y = -y;
144        }
145        ExtendedGcd {
146            g: b.unsigned(),
147            x,
148            y,
149        }
150    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 78)

75    pub fn trim_tail_zeros(&mut self) {
76        let mut len = self.length();
77        while len > 0 {
78            if self.data[len - 1].is_zero() {
79                len -= 1;
80            } else {
81                break;
82            }
83        }
84        self.truncate(len);
85    }
86}
87
88impl<T, C> Zero for FormalPowerSeries<T, C>
89where
90    T: PartialEq,
91{
92    fn zero() -> Self {
93        Self::from_vec(Vec::new())
94    }
95}
96impl<T, C> One for FormalPowerSeries<T, C>
97where
98    T: PartialEq + One,
99{
100    fn one() -> Self {
101        Self::from(T::one())
102    }
103}
104
105impl<T, C> IntoIterator for FormalPowerSeries<T, C> {
106    type Item = T;
107    type IntoIter = std::vec::IntoIter<T>;
108    fn into_iter(self) -> Self::IntoIter {
109        self.data.into_iter()
110    }
111}
112impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C> {
113    type Item = &'a T;
114    type IntoIter = Iter<'a, T>;
115    fn into_iter(self) -> Self::IntoIter {
116        self.data.iter()
117    }
118}
119impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C> {
120    type Item = &'a mut T;
121    type IntoIter = IterMut<'a, T>;
122    fn into_iter(self) -> Self::IntoIter {
123        self.data.iter_mut()
124    }
125}
126
127impl<T, C> FromIterator<T> for FormalPowerSeries<T, C> {
128    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
129        Self::from_vec(iter.into_iter().collect())
130    }
131}
132
133impl<T, C> Index<usize> for FormalPowerSeries<T, C> {
134    type Output = T;
135    fn index(&self, index: usize) -> &Self::Output {
136        &self.data[index]
137    }
138}
139impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C> {
140    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
141        &mut self.data[index]
142    }
143}
144
145impl<T, C> From<T> for FormalPowerSeries<T, C> {
146    fn from(x: T) -> Self {
147        once(x).collect()
148    }
149}
150impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C> {
151    fn from(data: Vec<T>) -> Self {
152        Self::from_vec(data)
153    }
154}
155
156impl<T, C> FormalPowerSeries<T, C>
157where
158    T: FormalPowerSeriesCoefficient,
159{
160    pub fn prefix_ref(&self, deg: usize) -> Self {
161        if deg < self.length() {
162            Self::from_vec(self.data[..deg].to_vec())
163        } else {
164            self.clone()
165        }
166    }
167    pub fn prefix(mut self, deg: usize) -> Self {
168        self.data.truncate(deg);
169        self
170    }
171    pub fn even(mut self) -> Self {
172        let mut keep = false;
173        self.data.retain(|_| {
174            keep = !keep;
175            keep
176        });
177        self
178    }
179    pub fn odd(mut self) -> Self {
180        let mut keep = true;
181        self.data.retain(|_| {
182            keep = !keep;
183            keep
184        });
185        self
186    }
187    pub fn diff(mut self) -> Self {
188        let mut c = T::one();
189        for x in self.iter_mut().skip(1) {
190            *x *= &c;
191            c += T::one();
192        }
193        if self.length() > 0 {
194            self.data.remove(0);
195        }
196        self
197    }
198    pub fn integral(mut self) -> Self {
199        let n = self.length();
200        self.data.insert(0, Zero::zero());
201        let mut fact = Vec::with_capacity(n + 1);
202        let mut c = T::one();
203        fact.push(c.clone());
204        for _ in 1..n {
205            fact.push(fact.last().cloned().unwrap() * c.clone());
206            c += T::one();
207        }
208        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
209        for x in self.iter_mut().skip(1).rev() {
210            *x *= invf.clone() * fact.pop().unwrap();
211            invf *= c.clone();
212            c -= T::one();
213        }
214        self
215    }
216    pub fn parity_inversion(mut self) -> Self {
217        self.iter_mut()
218            .skip(1)
219            .step_by(2)
220            .for_each(|x| *x = -x.clone());
221        self
222    }
223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }

crates/competitive/src/algorithm/chromatic_number.rs (line 27)

19    pub fn k_colorable(&self, k: usize) -> bool {
20        !self
21            .ind
22            .iter()
23            .map(|d| d.pow(k))
24            .enumerate()
25            .map(|(s, d)| if s.count_ones() % 2 == 0 { d } else { -d })
26            .sum::<MInt<M>>()
27            .is_zero()
28    }

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    }

crates/competitive/src/num/rational.rs (line 42)

41    fn cmp(&self, other: &Self) -> Ordering {
42        match (self.den.is_zero(), other.den.is_zero()) {
43            (true, true) => self.num.cmp(&other.num),
44            (true, false) => self.num.cmp(&T::zero()),
45            (false, true) => T::zero().cmp(&other.num),
46            (false, false) => (self.num * other.den).cmp(&(self.den * other.num)),
47        }
48    }

crates/competitive/src/num/urational.rs (line 42)

41    fn cmp(&self, other: &Self) -> Ordering {
42        match (self.den.is_zero(), other.den.is_zero()) {
43            (true, true) => self.num.cmp(&other.num),
44            (true, false) => self.num.cmp(&T::zero()),
45            (false, true) => T::zero().cmp(&other.num),
46            (false, false) => (self.num * other.den).cmp(&(self.den * other.num)),
47        }
48    }