自动取模数板子

用法

字面意思，自动对一个数取模。

其中内置了快速幂qpow(a,b)和求逆元inv(a)，其中求逆元使用exgcd实现。

除法使用的是inv(a)实现，自带一个小log，如果卡时间的话请自行处理逆元。

默认对 998244353 取模，如要修改请修改 pmod 变量的值。

使用 modnum name; 来定义一个自动取模数。

可以用 (modnum).val 来获得自动取模数的真实值(long long类型)。

已经重载好了用于 iostream 的 << , >> 流传输运算符, 可以直接使用 cin , cout 输出。

code

namespace modnum_space {
    typedef long long ll;
    const ll pmod = 998244353;

    struct modnum;
    modnum inv(modnum a);
    ll exgcd(ll a, ll b, ll &x, ll &y);
    modnum qpow(modnum a, modnum b, modnum p);

    struct modnum {
        ll val;
        modnum(){ val = 0; }
        modnum(ll a) { val = (a%pmod+pmod)%pmod; }
        modnum(int a) { val = (a%pmod+pmod)%pmod; }
        friend modnum operator + (const modnum &a, const modnum &b){ return (a.val+b.val)%pmod; }
        friend modnum operator - (const modnum &a, const modnum &b){ return (a.val-b.val+pmod)%pmod; }
        friend modnum operator * (const modnum &a, const modnum &b){ return (a.val*b.val)%pmod; }
        friend modnum operator / (const modnum &a, const modnum &b){ return (a.val*inv(b.val)).val%pmod; }
        friend modnum& operator += (modnum &a, const modnum &b){ return a = a+b; }
        friend modnum& operator -= (modnum &a, const modnum &b){ return a = a-b; }
        friend modnum& operator *= (modnum &a, const modnum &b){ return a = a*b; }
        friend modnum& operator /= (modnum &a, const modnum &b){ return a = a/b; }
    };

    modnum inv(modnum a)
    {
        ll x, y;
        exgcd(a.val, pmod, x, y);
        x = (x%pmod+pmod)%pmod;
        return x;
    }
    modnum qpow(modnum a, ll b)
    {
        modnum ans = 1;
        for(; b; b >>= 1, a *= a)
            if(b&1) ans *= a;
        return ans;
    }
    ll exgcd(ll a, ll b, ll &x, ll &y)
    {
        if(b == 0){ return x = 1, y = 0, a; }
        ll d = exgcd(b, a%b, x, y);
        ll z = x; x = y; y = z-(a/b)*y;
        return d;
    }


    #ifdef _GLIBCXX_IOSTREAM
    std::istream& operator >> (std::istream& cin, modnum &a)
    { cin >> a.val; a.val %= pmod; return cin; }
    std::ostream& operator << (std::ostream& cout, modnum a)
    { cout << a.val; return cout; }
    #endif
}
using namespace modnum_space;