library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kk2a/library

:heavy_check_mark: modint/mont.hpp

Depends on

Required by

Verified with

Code

#ifndef KK2_MODINT_MONT_HPP
#define KK2_MODINT_MONT_HPP 1

#include <cassert>
#include <cstdint>
#include <iostream>
#include <type_traits>

#include "../type_traits/integral.hpp"
#include "../type_traits/io.hpp"

namespace kk2 {

template <int p> struct LazyMontgomeryModInt {
    using mint = LazyMontgomeryModInt;
    using i32 = int32_t;
    using i64 = int64_t;
    using u32 = uint32_t;
    using u64 = uint64_t;

    static constexpr u32 get_r() {
        u32 ret = p;
        for (int i = 0; i < 4; ++i) ret *= 2 - p * ret;
        return ret;
    }

    static constexpr u32 r = get_r();
    static constexpr u32 n2 = -u64(p) % p;
    static_assert(r * p == 1, "invalid, r * p != 1");
    static_assert(p < (1 << 30), "invalid, p >= 2 ^ 30");
    static_assert((p & 1) == 1, "invalid, p % 2 == 0");

    u32 _v;

    constexpr LazyMontgomeryModInt() : _v(0) {}

    template <typename T, is_integral_t<T> * = nullptr> constexpr LazyMontgomeryModInt(T b)
        : _v(reduce(u64(b % p + p) * n2)) {}

    static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * p) >> 32; }
    constexpr mint &operator++() { return *this += 1; }
    constexpr mint &operator--() { return *this -= 1; }

    constexpr mint operator++(int) {
        mint ret = *this;
        *this += 1;
        return ret;
    }

    constexpr mint operator--(int) {
        mint ret = *this;
        *this -= 1;
        return ret;
    }

    constexpr mint &operator+=(const mint &b) {
        if (i32(_v += b._v - 2 * p) < 0) _v += 2 * p;
        return *this;
    }

    constexpr mint &operator-=(const mint &b) {
        if (i32(_v -= b._v) < 0) _v += 2 * p;
        return *this;
    }

    constexpr mint &operator*=(const mint &b) {
        _v = reduce(u64(_v) * b._v);
        return *this;
    }

    constexpr mint &operator/=(const mint &b) {
        *this *= b.inv();
        return *this;
    }


    constexpr bool operator==(const mint &b) const {
        return (_v >= p ? _v - p : _v) == (b._v >= p ? b._v - p : b._v);
    }

    constexpr bool operator!=(const mint &b) const {
        return (_v >= p ? _v - p : _v) != (b._v >= p ? b._v - p : b._v);
    }

    constexpr mint operator-() const { return mint() - mint(*this); }
    constexpr mint operator+() const { return mint(*this); }
    friend constexpr mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    friend constexpr mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    friend constexpr mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    friend constexpr mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }

    template <class T> constexpr mint pow(T n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            if (n >>= 1) mul *= mul;
        }
        return ret;
    }

    constexpr mint inv() const {
        assert(*this != mint(0));
        return pow(p - 2);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const mint &x) {
        return os << x.val();
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, mint &x) {
        i64 t;
        is >> t;
        x = mint(t);
        return (is);
    }

    constexpr u32 val() const {
        u32 ret = reduce(_v);
        return ret >= p ? ret - p : ret;
    }

    static constexpr u32 getmod() { return p; }
};

template <int p> using Mont = LazyMontgomeryModInt<p>;

using mont998 = Mont<998244353>;
using mont107 = Mont<1000000007>;

} // namespace kk2

#endif // KK2_MODINT_MONT_HPP
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: type_traits/integral.hpp: line 4: #pragma once found in a non-first line
Back to top page