competitive-programming-rs 0.1.9

Competitive Programming Library in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

use std::ops::{Add, Rem, Sub, Mul};

#[derive(Copy)]
pub struct ModInt<T> {
    value: T,
    modulo: T,
}

impl<T> Clone for ModInt<T> where T: Copy {
    fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo } }

    fn clone_from(&mut self, source: &ModInt<T>) {
        self.value = source.value;
        self.modulo = source.modulo;
    }
}

impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output=T> + Sub<Output=T> + Copy + PartialOrd {
    type Output = ModInt<T>;

    fn add(self, rhs: ModInt<T>) -> ModInt<T> {
        let m = rhs.modulo;
        let mut t = rhs.value + self.value;
        if t > m { t = t - m; }
        ModInt { value: t, modulo: self.modulo }
    }
}

impl<T> Add<T> for ModInt<T> where T: Add<Output=T> + Sub<Output=T> + Copy + PartialOrd {
    type Output = ModInt<T>;

    fn add(self, rhs: T) -> ModInt<T> {
        let m = self.modulo;
        let mut t = rhs + self.value;
        if t > m { t = t - m; }
        ModInt { value: t, modulo: self.modulo }
    }
}

impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output=T> + Rem<Output=T> + Copy {
    type Output = ModInt<T>;

    fn mul(self, rhs: ModInt<T>) -> ModInt<T> {
        let t = (self.value * rhs.value) % self.modulo;
        ModInt { value: t, modulo: self.modulo }
    }
}

impl<T> Mul<T> for ModInt<T> where T: Mul<Output=T> + Rem<Output=T> + Copy {
    type Output = ModInt<T>;

    fn mul(self, rhs: T) -> ModInt<T> {
        let t = (self.value * rhs) % self.modulo;
        ModInt { value: t, modulo: self.modulo }
    }
}

impl<T> ModInt<T> {
    pub fn new(value: T, modulo: T) -> ModInt<T> {
        ModInt { value: value, modulo: modulo }
    }
}


#[cfg(test)]
mod test {
    extern crate rand;

    use super::*;
    use self::rand::distributions::{IndependentSample, Range};


    #[test]
    fn random_add() {
        let modulo = 1_000_000_007;
        let between = Range::new(0, modulo);
        let mut rng = rand::thread_rng();
        for _ in 0..1000 {
            let x = between.ind_sample(&mut rng);
            let y = between.ind_sample(&mut rng);

            let mx = ModInt::new(x, modulo);
            let my = ModInt::new(y, modulo);

            assert_eq!((mx + my).value, (x + y) % modulo);
            assert_eq!((mx + y).value, (x + y) % modulo);
        }
    }

    #[test]
    fn random_mul() {
        let modulo = 1_000_000_007;
        let between = Range::new(0, modulo);
        let mut rng = rand::thread_rng();
        for _ in 0..1000 {
            let x: usize = between.ind_sample(&mut rng);
            let y: usize = between.ind_sample(&mut rng);

            let mx = ModInt::new(x, modulo);
            let my = ModInt::new(y, modulo);

            assert_eq!((mx * my).value, (x * y) % modulo);
            assert_eq!((mx * y).value, (x * y) % modulo);
        }
    }
}