modint/dynamic-modint.hpp

• View this file on GitHub
• Last update: 2023-10-01 12:14:26+09:00
• Include: #include "modint/dynamic-modint.hpp"
• Link: https://atcoder.jp/contests/arc104/submissions/38888866

Depends on

• Barrett Reduction (math/barrett-reduction.hpp)

Code

#pragma once

#include <cassert>
#include <istream>
#include <ostream>

#include "../math/barrett-reduction.hpp"

// verify: https://atcoder.jp/contests/arc104/submissions/38888866
class DynamicModInt {
  public:
    DynamicModInt() : x(0) {}
    DynamicModInt(long long y)
        : x(y >= 0
                ? y % (long long)mod
                : ((long long)mod - (-y) % (long long)mod) % (long long)mod) {}
    static void set_mod(unsigned int m) {
        assert(m > 0);
        mod = m;
        bt = BarrettReduction(m);
    }
    unsigned int val() const { return x; }
    DynamicModInt &operator+=(const DynamicModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    DynamicModInt &operator-=(const DynamicModInt &p) {
        if((x += (mod - p.x)) >= mod) x -= mod;
        return *this;
    }
    DynamicModInt &operator*=(const DynamicModInt &p) {
        x = bt.mul(x, p.x);
        return *this;
    }
    DynamicModInt &operator/=(const DynamicModInt &p) {
        *this *= p.inv();
        return *this;
    }
    DynamicModInt operator-() const { return DynamicModInt(-x); }
    DynamicModInt operator+(const DynamicModInt &p) const {
        return DynamicModInt(*this) += p;
    }
    DynamicModInt operator-(const DynamicModInt &p) const {
        return DynamicModInt(*this) -= p;
    }
    DynamicModInt operator*(const DynamicModInt &p) const {
        return DynamicModInt(*this) *= p;
    }
    DynamicModInt operator/(const DynamicModInt &p) const {
        return DynamicModInt(*this) /= p;
    }
    bool operator==(const DynamicModInt &p) const { return x == p.x; }
    bool operator!=(const DynamicModInt &p) const { return x != p.x; }
    DynamicModInt inv() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        assert(a == 1 && "gcd(x, mod) must be '1'.");
        return DynamicModInt(u);
    }
    DynamicModInt pow(long long n) const {
        assert(n >= 0);
        DynamicModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const DynamicModInt &p) {
        return os << p.x;
    }
    friend std::istream &operator>>(std::istream &is, DynamicModInt &a) {
        long long t;
        is >> t;
        a = DynamicModInt(t);
        return (is);
    }
    static unsigned int get_mod() { return mod; }

  private:
    unsigned int x;
    static inline unsigned int mod;
    static inline BarrettReduction bt;
};

#line 2 "modint/dynamic-modint.hpp"

#include <cassert>
#include <istream>
#include <ostream>

#line 2 "math/barrett-reduction.hpp"

#include <utility>

class BarrettReduction {
public:
    BarrettReduction(): BarrettReduction(1) {}
    BarrettReduction(unsigned int m)
        : m(m), m_inv((unsigned long long)(-1) / m + 1) {}
    unsigned int mul(unsigned int a, unsigned int b) const {
        unsigned long long z = (unsigned long long)a * b;
        unsigned long long v =  (unsigned long long)(((__uint128_t)z * m_inv) >> 64);
        unsigned int result = (unsigned int)(z - v * m);
        if(m <= result) result += m;
        return result;
    }
    unsigned int quo(unsigned int a) const {
        unsigned int result = (unsigned int)(((__uint128_t)a * m_inv) >> 64);
        return result;
    }
    unsigned int rem(unsigned long long a) const {
        unsigned long long v = (unsigned long long)(((__uint128_t)a * m_inv) >> 64);
        unsigned int result = (unsigned int)(a - v * m);
        if(m <= result) result += m;
        return result;
    }
    std::pair<unsigned int, unsigned int> quorem(unsigned int a) const {
        unsigned long long v =  (unsigned long long)(((__uint128_t)a * m_inv) >> 64);
        unsigned int r = (unsigned int)((unsigned long long)a - v * m);
        if(m <= r) r += m;
        return {v, r};
    }
private:
    unsigned int m;
    unsigned long long m_inv;
};
#line 8 "modint/dynamic-modint.hpp"

// verify: https://atcoder.jp/contests/arc104/submissions/38888866
class DynamicModInt {
  public:
    DynamicModInt() : x(0) {}
    DynamicModInt(long long y)
        : x(y >= 0
                ? y % (long long)mod
                : ((long long)mod - (-y) % (long long)mod) % (long long)mod) {}
    static void set_mod(unsigned int m) {
        assert(m > 0);
        mod = m;
        bt = BarrettReduction(m);
    }
    unsigned int val() const { return x; }
    DynamicModInt &operator+=(const DynamicModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    DynamicModInt &operator-=(const DynamicModInt &p) {
        if((x += (mod - p.x)) >= mod) x -= mod;
        return *this;
    }
    DynamicModInt &operator*=(const DynamicModInt &p) {
        x = bt.mul(x, p.x);
        return *this;
    }
    DynamicModInt &operator/=(const DynamicModInt &p) {
        *this *= p.inv();
        return *this;
    }
    DynamicModInt operator-() const { return DynamicModInt(-x); }
    DynamicModInt operator+(const DynamicModInt &p) const {
        return DynamicModInt(*this) += p;
    }
    DynamicModInt operator-(const DynamicModInt &p) const {
        return DynamicModInt(*this) -= p;
    }
    DynamicModInt operator*(const DynamicModInt &p) const {
        return DynamicModInt(*this) *= p;
    }
    DynamicModInt operator/(const DynamicModInt &p) const {
        return DynamicModInt(*this) /= p;
    }
    bool operator==(const DynamicModInt &p) const { return x == p.x; }
    bool operator!=(const DynamicModInt &p) const { return x != p.x; }
    DynamicModInt inv() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        assert(a == 1 && "gcd(x, mod) must be '1'.");
        return DynamicModInt(u);
    }
    DynamicModInt pow(long long n) const {
        assert(n >= 0);
        DynamicModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const DynamicModInt &p) {
        return os << p.x;
    }
    friend std::istream &operator>>(std::istream &is, DynamicModInt &a) {
        long long t;
        is >> t;
        a = DynamicModInt(t);
        return (is);
    }
    static unsigned int get_mod() { return mod; }

  private:
    unsigned int x;
    static inline unsigned int mod;
    static inline BarrettReduction bt;
};

Back to top page