跳转至

ModNum

普通情况下更推荐使用常用缺省源里的 MTool，更加方便好用，只需要更改 Mod 的值。

定模数版本

只需要修改 const 的那个 \(Mod\) 的值就行，输入输出需要加上 \(.x\)。

 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
namespace MInt
{
    static const int Mod=998244353;
    template<const int Mod> struct ModInt
    {
        int x;
        ModInt(int X=0):x(X) {}
        inline ModInt operator = (int &T) {*this.x=T; return *this;}
        inline ModInt operator = (const ModInt &T) {this->x=T.x; return *this;}
        inline friend ModInt operator + (ModInt a,ModInt b) {return a.x+b.x>=Mod?a.x+b.x-Mod:a.x+b.x;}
        inline friend ModInt operator - (ModInt a,ModInt b) {return a.x-b.x<0?a.x-b.x+Mod:a.x-b.x;}
        inline friend ModInt operator * (ModInt a,ModInt b) {return a.x*b.x%Mod;}
        inline friend ModInt operator ^ (ModInt a,int b) {ModInt res=1; while(b) {if(b&1) res=res*a; a=a*a; b>>=1;} return res;}
        inline friend ModInt operator / (ModInt a,ModInt b) {return a*(b^(Mod-2));}
        inline ModInt operator += (const ModInt &T) {*this=*this+T; return *this;}
        inline ModInt operator -= (const ModInt &T) {*this=*this-T; return *this;}
        inline ModInt operator *= (const ModInt &T) {*this=*this*T; return *this;}
        inline ModInt operator ^= (const ModInt &T) {*this=*this^T; return *this;}
        inline ModInt operator /= (const ModInt &T) {*this=*this/T; return *this;}
        template<typename T> inline friend ModInt operator + (ModInt a,T x) {return a+ModInt(x);}
        template<typename T> inline friend ModInt operator - (ModInt a,T x) {return a-ModInt(x);}
        template<typename T> inline friend ModInt operator * (ModInt a,T x) {return a*ModInt(x);}
        template<typename T> inline friend ModInt operator / (ModInt a,T x) {return a/ModInt(x);}
        inline friend bool operator == (ModInt a,ModInt b) {return a.x==b.x;}
        inline friend bool operator != (ModInt a,ModInt b) {return a.x!=b.x;}
        inline friend bool operator >  (ModInt a,ModInt b) {return a.x>b.x;}
        inline friend bool operator <  (ModInt a,ModInt b) {return a.x<b.x;}
        inline friend bool operator >= (ModInt a,ModInt b) {return a>b||a==b;}
        inline friend bool operator <= (ModInt a,ModInt b) {return a<b||a==b;}
        template<typename T> inline friend bool operator == (ModInt a,T b) {return a==ModInt(b);}
        template<typename T> inline friend bool operator != (ModInt a,T b) {return a!=ModInt(b);}
        template<typename T> inline friend bool operator >  (ModInt a,T b) {return a>ModInt(b);}
        template<typename T> inline friend bool operator <  (ModInt a,T b) {return a<ModInt(b);}
        template<typename T> inline friend bool operator >= (ModInt a,T b) {return a>=ModInt(b);}
        template<typename T> inline friend bool operator <= (ModInt a,T b) {return a<=ModInt(b);}
        inline bool operator ! () {return !x;}
        inline ModInt operator - () {return x?Mod-x:0;}
    };
}

可变模数

更改模数调用 ChangeMod。

 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
struct ModNum
{
    #define TA template<typename T,typename... Args>
    #define TT template<typename T>
    struct fastmod
    {
        using u128=__uint128_t; using u64=uint64_t; using u32=signed;
        u32 f,l; u64 m,d;
        fastmod(u64 D=998244353):d(D) 
        {
            const u128 ONE=1;
            l=64-__builtin_clzll(d-1);
            u128 M=((ONE<<(64+l))+(ONE<<l))/d;
            if(M<(ONE<<64)) f=1,m=M; else f=0,m=M-(ONE<<64);
        }
        inline friend u64 operator / (u64 x,const fastmod &y)
        {
            if(y.f) return u128(x)*y.m>>64>>y.l;
            else return (((x-(u128(x)*y.m>>64))>>1)+(u128(x)*y.m>>64))>>(y.l-1);
        }
        inline friend u64 operator % (u64 x,const fastmod &y)
        {
            return x-x/y*y.d;
        }
        inline friend u64 operator + (u64 x,const fastmod &y) {return x+y.d;}
        inline friend u64 operator - (u64 x,const fastmod &y) {return x-y.d;}
        inline friend bool operator == (u64 x,const fastmod &y) {return x==y.d;}
        inline friend bool operator >  (u64 x,const fastmod &y) {return x>y.d;}
        inline friend bool operator <  (u64 x,const fastmod &y) {return x<y.d;}
        inline friend bool operator >= (u64 x,const fastmod &y) {return x>y.d||x==y.d;}
        inline friend bool operator <= (u64 x,const fastmod &y) {return x<y.d||x==y.d;}
    };
    fastmod Mod;
    inline void ChangeMod(int MOD){Mod=MOD;}
    TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
    TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
    TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
    TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
    TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
    TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
    TT inline T Cmul(T a,T b) {return a*b%Mod;}
    TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
    TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
    TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
    TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
    TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
    TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
    TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
    TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
    TT inline T Ginv(T x)     {return qpow(x,(T)(Mod.d-2));}
    #undef TT
    #undef TA
};