QMath/Modular at main · ForAurie/QMath · GitHub

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
#ifndef MODULAR_H
#define MODULAR_H
#include <iostream>
namespace QMath {
    template <typename T = int, const T MOD = 998244353, typename MCT = unsigned long long>
    class Modular {
    private:
        T value;
    public:
        constexpr Modular(const T& v = T(0)) : value(v % MOD) { if (value < T(0)) value += MOD; }
        constexpr Modular(const Modular& other) : value(other.value) {}
        Modular& operator=(const Modular& other) { value = other.value; return *this; }
        Modular& operator=(const T& v) { value = v % MOD; if (value < T(0)) value += MOD; return *this; }

        T getVal() const { return value; }
        Modular& setVal(const T& v) { value = v % MOD; if (value < T(0)) value += MOD; return *this; }

        Modular operator-() const {
            Modular res(*this);
            if (res.value != T(0)) res.value = MOD - res.value;
            return res;
        }
        friend Modular operator+(const Modular& a, const Modular& b) {
            Modular res(a);
            if ((res.value += b.value) >= MOD) res.value -= MOD;
            return res;
        }
        friend Modular operator-(const Modular& a, const Modular& b) {
            Modular res(a);
            if ((res.value -= b.value) < T(0)) res.value += MOD;
            return res;
        }
        friend Modular operator*(const Modular& a, const Modular& b) { return Modular((MCT) a.value * (MCT) b.value % MOD); }
        Modular& operator+=(const Modular& other) {
            if ((value += other.value) >= MOD) value -= MOD;
            return *this;
        }
        Modular& operator-=(const Modular& other) {
            if ((value -= other.value) < T(0)) value += MOD;
            return *this;
        }
        Modular& operator*=(const Modular& other) {
            value = (MCT) value * (MCT) other.value % MOD;
            return *this;
        }
        template <typename U>
        Modular fPow(U exp) const {
            Modular result(1);
            T base = value;
            while (exp) {
                if (exp & 1) result.value = (MCT) result.value * (MCT) base % MOD;
                base = (MCT) base * (MCT) base % MOD;
                exp >>= 1;
            }
            return result;
        }
        template <typename U>
        Modular& fPowSelf(U exp) {
            T base = value;
            value = 1;
            while (exp) {
                if (exp & 1) value = (MCT) value * (MCT) base % MOD;
                base = (MCT) base * (MCT) base % MOD;
                exp >>= 1;
            }
            return *this;
        }
        Modular inv() const { return fPow(MOD - 2); }
        Modular& invSelf() { return fPowSelf(MOD - 2); }
        friend Modular operator/(const Modular& a, const Modular& b) { return a * b.inv(); }
        Modular& operator/=(const Modular& other) { return *this *= other.inv(); }

        friend bool operator==(const Modular& a, const Modular& b) { return a.value == b.value; }
        friend bool operator!=(const Modular& a, const Modular& b) { return a.value != b.value; }
        friend std::ostream& operator<<(std::ostream& os, const Modular& m) { return os << m.value; }
        friend std::istream& operator>>(std::istream& is, Modular& m) {
            T v;
            is >> v;
            m.setVal(v);
            return is;
        }
    };
}
#endif