ModValue (雑)

modular.rs

mod modular {
    // author: Leonardone @ NEETSDKASU

    // modulo for ModValue
    pub const MODULO: i64 = 1_000_000_007;

    #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
    pub struct ModValue {
        value: i64,
    }
    // ModValue::new(i64) -> Self
    // ModValue::pow(self, i64) -> Self
    // ModValue::inv(self) -> Self
    // ModValue::inv_flt(self) -> Self
    // ModValue::inv_eea(self) -> Option<Self>
    // From<ModValue> for i64
    // From<i64> for ModValue
    // Add,Sub,Mul,Div

    pub fn modinv(v: i64, modulo: i64) -> i64 {
        if cfg!(using_modinv_eea) {
            // Extended Euclidean Algorithm (gcd(v,modulo) == 1)
            modinv_eea(v, modulo).unwrap()
        } else {
            // Fermat's little theorem (modulo must be prime)
            modinv_flt(v, modulo)
        }
    }

    // exp >= 0
    pub fn modpow(v: i64, exp: i64, modulo: i64) -> i64 {
        if exp == 0 {
            1
        } else if (exp & 1) == 0 {
            modpow(v * v % modulo, exp >> 1, modulo)
        } else {
            v * modpow(v, exp ^ 1, modulo) % modulo
        }
    }

    // Extended Euclidean Algorithm
    //   compute: m*x + n*y = gcd(m, n)
    //   return: (x, y, gcd(m, n))
    pub fn extended_euclidean(mut m: i64, mut n: i64) -> (i64, i64, i64) {
        if m < n {
            let (y, x, gcd) = extended_euclidean(n, m);
            return (x, y, gcd);
        }
        assert!(m >= n);
        let mut x = 1;
        let mut y = 0;
        let mut u = 0;
        let mut v = 1;
        while n != 0 {
            let k = m / n;
            // [0  1] [x y]  [0*x+1*u  0*y+1*v]
            // [1 -k] [u v]  [1*x-k*u  1*y-k*v]
            let tx = u;
            let ty = v;
            let tu = x - k * u;
            let tv = y - k * v;
            x = tx;
            y = ty;
            u = tu;
            v = tv;
            let t = m % n;
            m = n;
            n = t;
        }
        (x, y, m)
    }

    // calc modular multiplicative inverse
    //   by Fermat's little theorem
    pub fn modinv_flt(v: i64, prime_modulo: i64) -> i64 {
        modpow(v, prime_modulo - 2, prime_modulo)
    }

    // calc modular multiplicative inverse
    //   by Extended Euclidean Algorithm
    pub fn modinv_eea(v: i64, modulo: i64) -> Option<i64> {
        let (x, _, gcd) = extended_euclidean(v, modulo);
        if gcd == 1 {
            Some(x)
        } else {
            None
        }
    }

    impl ModValue {
        pub fn new(value: i64) -> Self {
            Self {
                value: if value < MODULO {
                    value
                } else {
                    value % MODULO
                },
            }
        }

        pub fn pow(self, exp: i64) -> Self {
            Self {
                value: modpow(self.value, exp, MODULO),
            }
        }

        pub fn inv_flt(self) -> Self {
            Self {
                value: modinv_flt(self.value, MODULO),
            }
        }

        pub fn inv_eea(self) -> Option<Self> {
            modinv_eea(self.value, MODULO).map(|value| Self { value })
        }

        pub fn inv(self) -> Self {
            Self {
                value: modinv(self.value, MODULO),
            }
        }
    }

    impl From<i64> for ModValue {
        fn from(value: i64) -> Self {
            Self::new(value)
        }
    }

    impl From<ModValue> for i64 {
        fn from(mod_value: ModValue) -> i64 {
            mod_value.value
        }
    }

    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    impl Add for ModValue {
        type Output = Self;
        fn add(self, other: Self) -> Self::Output {
            (self.value + other.value).into()
        }
    }

    impl AddAssign for ModValue {
        fn add_assign(&mut self, other: Self) {
            *self = *self + other;
        }
    }

    impl Sub for ModValue {
        type Output = Self;
        fn sub(self, other: Self) -> Self::Output {
            (self.value + (MODULO - other.value)).into()
        }
    }

    impl SubAssign for ModValue {
        fn sub_assign(&mut self, other: Self) {
            *self = *self - other;
        }
    }

    impl Mul for ModValue {
        type Output = Self;
        fn mul(self, other: Self) -> Self::Output {
            (self.value * other.value).into()
        }
    }

    impl MulAssign for ModValue {
        fn mul_assign(&mut self, other: Self) {
            *self = *self * other;
        }
    }

    impl Div for ModValue {
        type Output = Self;
        fn div(self, other: Self) -> Self::Output {
            self.mul(other.inv())
        }
    }

    impl DivAssign for ModValue {
        fn div_assign(&mut self, other: Self) {
            *self = *self / other;
        }
    }
}