proconlib
This documentation is automatically generated by competitive-verifier/competitive-verifier
tests/rational/plus.test.cpp
- View this file on GitHub
- Last update: 2025-05-10 11:56:09+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_2_A
Depends on
- std::abs(x) extended for my library (tools/abs.hpp)
- Arbitrary precision floating-point number (tools/bigdecimal.hpp)
- Arbitrary precision integer (tools/bigint.hpp)
- $2^{\left\lceil \log_2(x) \right\rceil}$ (tools/bit_ceil.hpp)
- $2^{\left\lfloor \log_2(x) \right\rfloor}$ (tools/bit_floor.hpp)
- Bit width required to represent a given integer (tools/bit_width.hpp)
- $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
- chmin function (tools/chmin.hpp)
- Number of trailing zeros (tools/countr_zero.hpp)
- tools/detail/int128_t.hpp
- $\left\lfloor \frac{x}{y} \right\rfloor$ (tools/floor.hpp)
- $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
- Garner's algorithm for $\mathbb{Z} / M_1 \mathbb{Z}$ and $\mathbb{Z} / M_2 \mathbb{Z}$ (tools/garner2.hpp)
- std::gcd(m, n) extended for my library (tools/gcd.hpp)
- Combine hash values (tools/hash_combine.hpp)
- 128-bit signed integer (tools/int128_t.hpp)
- std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
- Miller-Rabin primality test (tools/is_prime.hpp)
- Check whether T is tools::rational (tools/is_rational.hpp)
- std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
- std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
- std::make_signed extended for tools::int128_t and tools::uint128_t (tools/make_signed.hpp)
- std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
- Minimum non-negative reminder (tools/mod.hpp)
- The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
- $2^x$ (tools/pow2.hpp)
- $x^y \pmod{M}$ (tools/pow_mod.hpp)
- $x \cdot y \pmod{M}$ (tools/prod_mod.hpp)
- Quotient as integer division (tools/quo.hpp)
- Rational number (tools/rational.hpp)
- Rounding mode (tools/rounding_mode.hpp)
- Sign function (tools/signum.hpp)
- 128-bit unsigned integer (tools/uint128_t.hpp)
Code
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/NTL_2_A
#include <iostream>
#include "tools/rational.hpp"
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
tools::rational A, B;
std::cin >> A >> B;
std::cout << (A + B).numerator() << '\n';
return 0;
}
#line 1 "tests/rational/plus.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/NTL_2_A
#include <iostream>
#line 1 "tools/rational.hpp"
#include <algorithm>
#include <cstddef>
#include <cassert>
#include <type_traits>
#include <limits>
#include <iterator>
#line 1 "tools/bigint.hpp"
#line 5 "tools/bigint.hpp"
#include <array>
#line 7 "tools/bigint.hpp"
#include <cmath>
#line 9 "tools/bigint.hpp"
#include <cstdint>
#line 11 "tools/bigint.hpp"
#include <string>
#include <tuple>
#include <iomanip>
#line 17 "tools/bigint.hpp"
#include <utility>
#include <vector>
#line 1 "lib/ac-library/atcoder/convolution.hpp"
#line 9 "lib/ac-library/atcoder/convolution.hpp"
#line 1 "lib/ac-library/atcoder/internal_bit.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
#line 1 "lib/ac-library/atcoder/modint.hpp"
#line 5 "lib/ac-library/atcoder/modint.hpp"
#include <numeric>
#line 7 "lib/ac-library/atcoder/modint.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
#line 1 "lib/ac-library/atcoder/internal_math.hpp"
#line 5 "lib/ac-library/atcoder/internal_math.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#line 1 "lib/ac-library/atcoder/internal_type_traits.hpp"
#line 7 "lib/ac-library/atcoder/internal_type_traits.hpp"
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#line 14 "lib/ac-library/atcoder/modint.hpp"
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#line 12 "lib/ac-library/atcoder/convolution.hpp"
namespace atcoder {
namespace internal {
template <class mint,
int g = internal::primitive_root<mint::mod()>,
internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
static constexpr int rank2 = countr_zero_constexpr(mint::mod() - 1);
std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[countr_zero(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].val();
auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[countr_zero(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
irot.val();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[countr_zero(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].val();
auto a1 = 1ULL * a[i + offset + 1 * p].val();
auto a2 = 1ULL * a[i + offset + 2 * p].val();
auto a3 = 1ULL * a[i + offset + 3 * p].val();
auto a2na3iimag =
1ULL *
mint((mint::mod() + a2 - a3) * iimag.val()).val();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
a[i + offset + 2 * p] =
(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
irot2.val();
a[i + offset + 3 * p] =
(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
irot3.val();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[countr_zero(~(unsigned int)(s))];
}
len -= 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_naive(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
std::vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace internal
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(std::move(a2), std::move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
static constexpr int MAX_AB_BIT = 24;
static_assert(MOD1 % (1ull << MAX_AB_BIT) == 1, "MOD1 isn't enough to support an array length of 2^24.");
static_assert(MOD2 % (1ull << MAX_AB_BIT) == 1, "MOD2 isn't enough to support an array length of 2^24.");
static_assert(MOD3 % (1ull << MAX_AB_BIT) == 1, "MOD3 isn't enough to support an array length of 2^24.");
assert(n + m - 1 <= (1 << MAX_AB_BIT));
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
// B = 2^63, -B <= x, r(real value) < B
// (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
// r = c1[i] (mod MOD1)
// focus on MOD1
// r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
// r = x,
// x - M' + (0 or 2B),
// x - 2M' + (0, 2B or 4B),
// x - 3M' + (0, 2B, 4B or 6B) (without mod!)
// (r - x) = 0, (0)
// - M' + (0 or 2B), (1)
// -2M' + (0 or 2B or 4B), (2)
// -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
// we checked that
// ((1) mod MOD1) mod 5 = 2
// ((2) mod MOD1) mod 5 = 3
// ((3) mod MOD1) mod 5 = 4
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder
#line 1 "tools/abs.hpp"
namespace tools {
constexpr float abs(const float x) {
return x < 0 ? -x : x;
}
constexpr double abs(const double x) {
return x < 0 ? -x : x;
}
constexpr long double abs(const long double x) {
return x < 0 ? -x : x;
}
constexpr int abs(const int x) {
return x < 0 ? -x : x;
}
constexpr long abs(const long x) {
return x < 0 ? -x : x;
}
constexpr long long abs(const long long x) {
return x < 0 ? -x : x;
}
constexpr unsigned int abs(const unsigned int x) {
return x;
}
constexpr unsigned long abs(const unsigned long x) {
return x;
}
constexpr unsigned long long abs(const unsigned long long x) {
return x;
}
}
#line 1 "tools/ceil.hpp"
#line 1 "tools/is_integral.hpp"
#line 5 "tools/is_integral.hpp"
namespace tools {
template <typename T>
struct is_integral : ::std::is_integral<T> {};
template <typename T>
inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}
#line 1 "tools/is_unsigned.hpp"
#line 5 "tools/is_unsigned.hpp"
namespace tools {
template <typename T>
struct is_unsigned : ::std::is_unsigned<T> {};
template <typename T>
inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}
#line 8 "tools/ceil.hpp"
namespace tools {
template <typename M, typename N> requires (
::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
assert(y != 0);
if (y >= 0) {
if (x > 0) {
return (x - 1) / y + 1;
} else {
if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
return 0;
} else {
return x / y;
}
}
} else {
if (x >= 0) {
if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
return 0;
} else {
return x / y;
}
} else {
return (x + 1) / y + 1;
}
}
}
}
#line 1 "tools/chmin.hpp"
#line 6 "tools/chmin.hpp"
namespace tools {
template <typename M, typename N>
bool chmin(M& lhs, const N& rhs) {
bool updated;
if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
updated = ::std::cmp_less(rhs, lhs);
} else {
updated = rhs < lhs;
}
if (updated) lhs = rhs;
return updated;
}
}
#line 1 "tools/floor.hpp"
#line 7 "tools/floor.hpp"
namespace tools {
template <typename M, typename N> requires (
::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
constexpr ::std::common_type_t<M, N> floor(const M x, const N y) noexcept {
assert(y != 0);
if (y >= 0) {
if (x >= 0) {
return x / y;
} else {
return (x + 1) / y - 1;
}
} else {
if (x > 0) {
return (x - 1) / y - 1;
} else {
return x / y;
}
}
}
}
#line 1 "tools/floor_log2.hpp"
#line 1 "tools/bit_width.hpp"
#include <bit>
#line 1 "tools/is_signed.hpp"
#line 5 "tools/is_signed.hpp"
namespace tools {
template <typename T>
struct is_signed : ::std::is_signed<T> {};
template <typename T>
inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}
#line 1 "tools/make_unsigned.hpp"
#line 5 "tools/make_unsigned.hpp"
namespace tools {
template <typename T>
struct make_unsigned : ::std::make_unsigned<T> {};
template <typename T>
using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}
#line 10 "tools/bit_width.hpp"
namespace tools {
template <typename T>
constexpr int bit_width(T) noexcept;
template <typename T>
constexpr int bit_width(const T x) noexcept {
static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
if constexpr (::tools::is_signed_v<T>) {
assert(x >= 0);
return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
} else {
return ::std::bit_width(x);
}
}
}
#line 6 "tools/floor_log2.hpp"
namespace tools {
template <typename T>
constexpr T floor_log2(T x) noexcept {
assert(x > 0);
return ::tools::bit_width(x) - 1;
}
}
#line 1 "tools/garner2.hpp"
#line 1 "tools/is_prime.hpp"
#line 1 "tools/prod_mod.hpp"
#line 1 "tools/uint128_t.hpp"
#line 1 "tools/detail/int128_t.hpp"
#line 8 "tools/detail/int128_t.hpp"
#include <functional>
#line 12 "tools/detail/int128_t.hpp"
#include <string_view>
#line 1 "tools/bit_ceil.hpp"
#line 10 "tools/bit_ceil.hpp"
namespace tools {
template <typename T>
constexpr T bit_ceil(T) noexcept;
template <typename T>
constexpr T bit_ceil(const T x) noexcept {
static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
if constexpr (::tools::is_signed_v<T>) {
assert(x >= 0);
return ::tools::bit_ceil<::tools::make_unsigned_t<T>>(x);
} else {
return ::std::bit_ceil(x);
}
}
}
#line 1 "tools/bit_floor.hpp"
#line 10 "tools/bit_floor.hpp"
namespace tools {
template <typename T>
constexpr T bit_floor(T) noexcept;
template <typename T>
constexpr T bit_floor(const T x) noexcept {
static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
if constexpr (::tools::is_signed_v<T>) {
assert(x >= 0);
return ::tools::bit_floor<::tools::make_unsigned_t<T>>(x);
} else {
return ::std::bit_floor(x);
}
}
}
#line 1 "tools/countr_zero.hpp"
#line 12 "tools/countr_zero.hpp"
namespace tools {
template <typename T>
constexpr int countr_zero(const T x) noexcept {
static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
if constexpr (::tools::is_signed_v<T>) {
assert(x >= 0);
return ::std::min(::tools::countr_zero<::tools::make_unsigned_t<T>>(x), ::std::numeric_limits<T>::digits);
} else {
return ::std::countr_zero(x);
}
}
}
#line 1 "tools/hash_combine.hpp"
#line 6 "tools/hash_combine.hpp"
// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.
// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
namespace tools {
template <typename T>
void hash_combine(::std::size_t& seed, const T& v) {
static const ::std::hash<T> hasher;
static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
::std::size_t a = (hasher(v) ^ seed) * k_mul;
a ^= (a >> 47);
::std::size_t b = (seed ^ a) * k_mul;
b ^= (b >> 47);
seed = b * k_mul;
}
}
#line 1 "tools/make_signed.hpp"
#line 5 "tools/make_signed.hpp"
namespace tools {
template <typename T>
struct make_signed : ::std::make_signed<T> {};
template <typename T>
using make_signed_t = typename ::tools::make_signed<T>::type;
}
#line 1 "tools/now.hpp"
#include <chrono>
namespace tools {
inline long long now() {
return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}
}
#line 25 "tools/detail/int128_t.hpp"
namespace tools {
using uint128_t = unsigned __int128;
using int128_t = __int128;
namespace detail {
namespace int128_t {
constexpr ::tools::uint128_t parse_unsigned(const ::std::string_view s) noexcept {
assert(!s.empty());
::tools::uint128_t x = 0;
::std::size_t i = s[0] == '+';
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x <<= 4;
if ('0' <= s[i] && s[i] <= '9') {
x |= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x |= s[i] - 'a' + 10;
} else {
x |= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x += s[i] - '0';
}
}
return x;
}
constexpr ::tools::int128_t parse_signed(const ::std::string_view s) noexcept {
assert(!s.empty());
::tools::int128_t x = 0;
if (s[0] == '-') {
::std::size_t i = 1;
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x *= 16;
if ('0' <= s[i] && s[i] <= '9') {
x -= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x -= s[i] - 'a' + 10;
} else {
x -= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x -= s[i] - '0';
}
}
} else {
::std::size_t i = s[0] == '+';
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x <<= 4;
if ('0' <= s[i] && s[i] <= '9') {
x |= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x |= s[i] - 'a' + 10;
} else {
x |= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x += s[i] - '0';
}
}
}
return x;
}
}
}
constexpr ::tools::uint128_t abs(const ::tools::uint128_t& x) noexcept {
return x;
}
constexpr ::tools::int128_t abs(const ::tools::int128_t& x) {
return x >= 0 ? x : -x;
}
}
#define UINT128_C(c) ::tools::detail::int128_t::parse_unsigned(#c)
#define INT128_C(c) ::tools::detail::int128_t::parse_signed(#c)
inline ::std::istream& operator>>(::std::istream& is, ::tools::uint128_t& x) {
::std::string s;
is >> s;
x = ::tools::detail::int128_t::parse_unsigned(s);
return is;
}
inline ::std::istream& operator>>(::std::istream& is, ::tools::int128_t& x) {
::std::string s;
is >> s;
x = ::tools::detail::int128_t::parse_signed(s);
return is;
}
inline ::std::ostream& operator<<(::std::ostream& os, ::tools::uint128_t x) {
::std::string s;
if (x > 0) {
while (x > 0) {
s.push_back('0' + x % 10);
x /= 10;
}
} else {
s.push_back('0');
}
::std::ranges::reverse(s);
return os << s;
}
inline ::std::ostream& operator<<(::std::ostream& os, ::tools::int128_t x) {
::std::string s;
if (x > 0) {
while (x > 0) {
s.push_back('0' + x % 10);
x /= 10;
}
} else if (x < 0) {
while (x < 0) {
s.push_back('0' + (-(x % 10)));
x /= 10;
}
s.push_back('-');
} else {
s.push_back('0');
}
::std::ranges::reverse(s);
return os << s;
}
#if defined(__GLIBCXX__) && defined(__STRICT_ANSI__)
namespace std {
template <>
struct hash<::tools::uint128_t> {
::std::size_t operator()(const ::tools::uint128_t& x) const {
static const ::std::size_t seed = ::tools::now();
::std::size_t hash = seed;
::tools::hash_combine(hash, static_cast<::std::uint64_t>(x >> 64));
::tools::hash_combine(hash, static_cast<::std::uint64_t>(x & ((UINT128_C(1) << 64) - 1)));
return hash;
}
};
template <>
struct hash<::tools::int128_t> {
::std::size_t operator()(const ::tools::int128_t& x) const {
static ::std::hash<::tools::uint128_t> hasher;
return hasher(static_cast<::tools::uint128_t>(x));
}
};
}
#endif
namespace tools {
template <>
struct is_integral<::tools::int128_t> : ::std::true_type {};
template <>
struct is_integral<::tools::uint128_t> : ::std::true_type {};
template <>
struct is_integral<const ::tools::int128_t> : ::std::true_type {};
template <>
struct is_integral<const ::tools::uint128_t> : ::std::true_type {};
template <>
struct is_integral<volatile ::tools::int128_t> : ::std::true_type {};
template <>
struct is_integral<volatile ::tools::uint128_t> : ::std::true_type {};
template <>
struct is_integral<const volatile ::tools::int128_t> : ::std::true_type {};
template <>
struct is_integral<const volatile ::tools::uint128_t> : ::std::true_type {};
template <>
struct is_signed<::tools::int128_t> : ::std::true_type {};
template <>
struct is_signed<::tools::uint128_t> : ::std::false_type {};
template <>
struct is_signed<const ::tools::int128_t> : ::std::true_type {};
template <>
struct is_signed<const ::tools::uint128_t> : ::std::false_type {};
template <>
struct is_signed<volatile ::tools::int128_t> : ::std::true_type {};
template <>
struct is_signed<volatile ::tools::uint128_t> : ::std::false_type {};
template <>
struct is_signed<const volatile ::tools::int128_t> : ::std::true_type {};
template <>
struct is_signed<const volatile ::tools::uint128_t> : ::std::false_type {};
template <>
struct is_unsigned<::tools::int128_t> : ::std::false_type {};
template <>
struct is_unsigned<::tools::uint128_t> : ::std::true_type {};
template <>
struct is_unsigned<const ::tools::int128_t> : ::std::false_type {};
template <>
struct is_unsigned<const ::tools::uint128_t> : ::std::true_type {};
template <>
struct is_unsigned<volatile ::tools::int128_t> : ::std::false_type {};
template <>
struct is_unsigned<volatile ::tools::uint128_t> : ::std::true_type {};
template <>
struct is_unsigned<const volatile ::tools::int128_t> : ::std::false_type {};
template <>
struct is_unsigned<const volatile ::tools::uint128_t> : ::std::true_type {};
template <>
struct make_signed<::tools::int128_t> {
using type = ::tools::int128_t;
};
template <>
struct make_signed<::tools::uint128_t> {
using type = ::tools::int128_t;
};
template <>
struct make_signed<const ::tools::int128_t> {
using type = const ::tools::int128_t;
};
template <>
struct make_signed<const ::tools::uint128_t> {
using type = const ::tools::int128_t;
};
template <>
struct make_signed<volatile ::tools::int128_t> {
using type = volatile ::tools::int128_t;
};
template <>
struct make_signed<volatile ::tools::uint128_t> {
using type = volatile ::tools::int128_t;
};
template <>
struct make_signed<const volatile ::tools::int128_t> {
using type = const volatile ::tools::int128_t;
};
template <>
struct make_signed<const volatile ::tools::uint128_t> {
using type = const volatile ::tools::int128_t;
};
template <>
struct make_unsigned<::tools::int128_t> {
using type = ::tools::uint128_t;
};
template <>
struct make_unsigned<::tools::uint128_t> {
using type = ::tools::uint128_t;
};
template <>
struct make_unsigned<const ::tools::int128_t> {
using type = const ::tools::uint128_t;
};
template <>
struct make_unsigned<const ::tools::uint128_t> {
using type = const ::tools::uint128_t;
};
template <>
struct make_unsigned<volatile ::tools::int128_t> {
using type = volatile ::tools::uint128_t;
};
template <>
struct make_unsigned<volatile ::tools::uint128_t> {
using type = volatile ::tools::uint128_t;
};
template <>
struct make_unsigned<const volatile ::tools::int128_t> {
using type = const volatile ::tools::uint128_t;
};
template <>
struct make_unsigned<const volatile ::tools::uint128_t> {
using type = const volatile ::tools::uint128_t;
};
#if defined(__GLIBCXX__) && defined(__STRICT_ANSI__)
template <>
constexpr ::tools::uint128_t bit_ceil<::tools::uint128_t>(::tools::uint128_t x) noexcept {
if (x <= 1) return 1;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
x |= x >> 64;
return ++x;
}
template <>
constexpr ::tools::uint128_t bit_floor<::tools::uint128_t>(::tools::uint128_t x) noexcept {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
x |= x >> 64;
return x & ~(x >> 1);
}
template <>
constexpr int bit_width<::tools::uint128_t>(::tools::uint128_t x) noexcept {
int w = 0;
if (x & UINT128_C(0xffffffffffffffff0000000000000000)) {
x >>= 64;
w += 64;
}
if (x & UINT128_C(0xffffffff00000000)) {
x >>= 32;
w += 32;
}
if (x & UINT128_C(0xffff0000)) {
x >>= 16;
w += 16;
}
if (x & UINT128_C(0xff00)) {
x >>= 8;
w += 8;
}
if (x & UINT128_C(0xf0)) {
x >>= 4;
w += 4;
}
if (x & UINT128_C(0xc)) {
x >>= 2;
w += 2;
}
if (x & UINT128_C(0x2)) {
x >>= 1;
w += 1;
}
w += x;
return w;
}
namespace detail {
namespace countr_zero {
template <::std::size_t N>
struct ntz_traits;
template <>
struct ntz_traits<128> {
using type = ::tools::uint128_t;
static constexpr int shift = 120;
static constexpr type magic = UINT128_C(0x01061438916347932a5cd9d3ead7b77f);
static constexpr int ntz_table[255] = {
128, 0, 1, -1, 2, -1, 8, -1, 3, -1, 15, -1, 9, -1, 22, -1,
4, -1, 29, -1, 16, -1, 36, -1, 10, -1, 43, -1, 23, -1, 50, -1,
5, -1, 33, -1, 30, -1, 57, -1, 17, -1, 64, -1, 37, -1, 71, -1,
11, -1, 60, -1, 44, -1, 78, -1, 24, -1, 85, -1, 51, -1, 92, -1,
-1, 6, -1, 20, -1, 34, -1, 48, 31, -1, -1, 69, 58, -1, -1, 90,
18, -1, 67, -1, 65, -1, 99, -1, 38, -1, 101, -1, 72, -1, 106, -1,
-1, 12, -1, 40, -1, 61, -1, 82, 45, -1, -1, 103, 79, -1, 113, -1,
-1, 25, -1, 74, 86, -1, -1, 116, -1, 52, -1, 108, -1, 93, -1, 120,
127, -1, -1, 7, -1, 14, -1, 21, -1, 28, -1, 35, -1, 42, -1, 49,
-1, 32, -1, 56, -1, 63, -1, 70, -1, 59, -1, 77, -1, 84, -1, 91,
-1, 19, -1, 47, -1, 68, -1, 89, -1, 66, -1, 98, -1, 100, -1, 105,
-1, 39, -1, 81, -1, 102, -1, 112, -1, 73, -1, 115, -1, 107, -1, 119,
126, -1, 13, -1, 27, -1, 41, -1, -1, 55, 62, -1, -1, 76, 83, -1,
-1, 46, -1, 88, -1, 97, -1, 104, -1, 80, -1, 111, -1, 114, -1, 118,
125, -1, 26, -1, 54, -1, 75, -1, -1, 87, 96, -1, -1, 110, -1, 117,
124, -1, 53, -1, -1, 95, 109, -1, 123, -1, 94, -1, 122, -1, 121
};
};
template <typename T>
constexpr int impl(const T x) noexcept {
using tr = ::tools::detail::countr_zero::ntz_traits<::std::numeric_limits<T>::digits>;
using type = typename tr::type;
return tr::ntz_table[static_cast<type>(tr::magic * static_cast<type>(x & -x)) >> tr::shift];
}
}
}
template <>
constexpr int countr_zero<::tools::uint128_t>(const ::tools::uint128_t x) noexcept {
return ::tools::detail::countr_zero::impl(x);
}
#endif
}
#line 5 "tools/uint128_t.hpp"
#line 5 "tools/prod_mod.hpp"
namespace tools {
template <typename T1, typename T2, typename T3>
constexpr T3 prod_mod(const T1 x, const T2 y, const T3 m) {
using u128 = ::tools::uint128_t;
u128 prod_mod = u128(x >= 0 ? x : -x) * u128(y >= 0 ? y : -y) % u128(m);
if ((x >= 0) ^ (y >= 0)) prod_mod = u128(m) - prod_mod;
return prod_mod;
}
}
#line 1 "tools/pow_mod.hpp"
#line 1 "tools/mod.hpp"
#line 7 "tools/mod.hpp"
namespace tools {
template <typename M, typename N> requires (
::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
assert(b != 0);
using UM = ::std::make_unsigned_t<M>;
using UN = ::std::make_unsigned_t<N>;
const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
auto r = ua % ub;
if (a < 0 && r > 0) {
r = ub - r;
}
return r;
}
}
#line 6 "tools/pow_mod.hpp"
namespace tools {
template <typename T1, typename T2, typename T3>
constexpr T3 pow_mod(const T1 x, T2 n, const T3 m) {
if (m == 1) return 0;
T3 r = 1;
T3 y = ::tools::mod(x, m);
while (n > 0) {
if ((n & 1) > 0) {
r = ::tools::prod_mod(r, y, m);
}
y = ::tools::prod_mod(y, y, m);
n /= 2;
}
return r;
}
}
#line 7 "tools/is_prime.hpp"
namespace tools {
constexpr bool is_prime(const unsigned long long n) {
constexpr ::std::array<unsigned long long, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
auto d = n - 1;
for (; d % 2 == 0; d /= 2);
for (const auto a : bases) {
if (a % n == 0) return true;
auto power = d;
auto target = ::tools::pow_mod(a, power, n);
bool is_composite = true;
if (target == 1) is_composite = false;
for (; is_composite && power != n - 1; power *= 2, target = ::tools::prod_mod(target, target, n)) {
if (target == n - 1) is_composite = false;
}
if (is_composite) {
return false;
}
}
return true;
}
}
#line 6 "tools/garner2.hpp"
namespace tools {
template <typename M1, typename M2>
long long garner2(const M1& a, const M2& b) {
using ull = unsigned long long;
static constexpr ull m1_m2 = ull(M1::mod()) * ull(M2::mod());
static const M2 m1_inv_mod_m2 = M2::raw(M1::mod()).inv();
assert(M1::mod() < M2::mod());
assert(::tools::is_prime(M1::mod()));
assert(::tools::is_prime(M2::mod()));
// t = (b - a) / M1; (mod M2)
// return a + t * M1;
const M2 t = (b - M2::raw(a.val())) * m1_inv_mod_m2;
ull r = t.val();
r *= M1::mod();
r += a.val();
if (r >= m1_m2) r -= m1_m2;
return r;
}
}
#line 1 "tools/gcd.hpp"
#line 6 "tools/gcd.hpp"
namespace tools {
template <typename M, typename N>
constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
return ::std::gcd(m, n);
}
}
#line 1 "tools/int128_t.hpp"
#line 5 "tools/int128_t.hpp"
#line 1 "tools/pow2.hpp"
#line 6 "tools/pow2.hpp"
namespace tools {
template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
constexpr T pow2(const T x) {
return static_cast<T>(1) << x;
}
template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
constexpr T pow2(const T x) {
return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
}
}
#line 1 "tools/quo.hpp"
#line 7 "tools/quo.hpp"
namespace tools {
template <typename M, typename N> requires (
::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
constexpr ::std::common_type_t<M, N> quo(const M a, const N b) noexcept {
assert(b != 0);
if (a >= 0) {
return a / b;
} else {
if (b >= 0) {
return (a + 1) / b - 1;
} else {
return (a + 1) / b + 1;
}
}
}
}
#line 33 "tools/bigint.hpp"
namespace tools {
class bigint;
::tools::bigint abs(::tools::bigint x);
class bigint {
private:
using mint1 = ::atcoder::static_modint<167772161>;
using mint2 = ::atcoder::static_modint<469762049>;
bool m_positive;
::std::vector<::std::int_fast32_t> m_digits;
static constexpr ::std::int_fast32_t BASE = 10000;
static constexpr ::std::int_fast32_t LOG10_BASE = 4;
static constexpr ::std::array<::std::int_fast32_t, 5> POW10 = {1, 10, 100, 1000, 10000};
static int compare_3way(const ::std::size_t lhs, const ::std::size_t rhs) {
if (lhs < rhs) return -1;
if (lhs == rhs) return 0;
return 1;
}
static int compare_3way_abs(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
if (const auto comp = ::tools::bigint::compare_3way(lhs.m_digits.size(), rhs.m_digits.size()); comp != 0) {
return comp;
}
for (::std::size_t i = lhs.m_digits.size(); i --> 0;) {
if (const auto comp = ::tools::bigint::compare_3way(lhs.m_digits[i], rhs.m_digits[i]); comp != 0) {
return comp;
}
}
return 0;
}
template <int LEVEL>
::tools::bigint& regularize() {
if constexpr (LEVEL > 0) {
if constexpr (LEVEL == 2) {
for (::std::size_t i = 0; i + 1 < this->m_digits.size(); ++i) {
this->m_digits[i + 1] += ::tools::quo(this->m_digits[i], BASE);
this->m_digits[i] = ::tools::mod(this->m_digits[i], BASE);
}
} else {
for (::std::size_t i = 0; i + 1 < this->m_digits.size(); ++i) {
if (this->m_digits[i] < 0) {
this->m_digits[i] += BASE;
--this->m_digits[i + 1];
} else if (this->m_digits[i] >= BASE) {
this->m_digits[i] -= BASE;
++this->m_digits[i + 1];
}
}
}
if (!this->m_digits.empty() && this->m_digits.back() < 0) {
this->m_positive = !this->m_positive;
for (::std::size_t i = 0; i < this->m_digits.size(); ++i) {
this->m_digits[i] = -this->m_digits[i];
}
for (::std::size_t i = 0; i + 1 < this->m_digits.size(); ++i) {
if (this->m_digits[i] < 0) {
this->m_digits[i] = BASE + this->m_digits[i];
--this->m_digits[i + 1];
}
}
}
if constexpr (LEVEL == 2) {
while (!this->m_digits.empty() && this->m_digits.back() >= BASE) {
this->m_digits.push_back(this->m_digits.back() / BASE);
this->m_digits[this->m_digits.size() - 2] %= BASE;
}
} else {
if (!this->m_digits.empty() && this->m_digits.back() >= BASE) {
this->m_digits.back() -= BASE;
this->m_digits.push_back(1);
}
}
}
while (!this->m_digits.empty() && this->m_digits.back() == 0) {
this->m_digits.pop_back();
}
if (this->m_digits.empty() && !this->m_positive) {
this->m_positive = true;
}
return *this;
}
public:
::tools::bigint& negate() {
if (!this->m_digits.empty()) {
this->m_positive = !this->m_positive;
}
return *this;
}
::tools::bigint& multiply_by_pow10(const ::std::ptrdiff_t exponent) {
if (!this->m_digits.empty()) {
const ::std::ptrdiff_t exponent10000 = ::tools::floor(exponent, LOG10_BASE);
::std::int_fast32_t mod = 0;
if (exponent10000 > 0) {
::std::vector<::std::int_fast32_t> zero(exponent10000, 0);
this->m_digits.insert(this->m_digits.begin(), zero.begin(), zero.end());
} else if (exponent10000 < 0) {
if (::std::ssize(this->m_digits) >= -exponent10000) {
mod = this->m_digits[-exponent10000 - 1] / POW10[LOG10_BASE * (exponent10000 + 1) - exponent];
}
this->m_digits.erase(this->m_digits.begin(), this->m_digits.begin() + ::std::min<::std::size_t>(-exponent10000, this->m_digits.size()));
}
if (const ::std::int_fast32_t coefficient = POW10[exponent - LOG10_BASE * exponent10000]; coefficient > POW10[0]) {
for (auto& d : this->m_digits) {
d *= coefficient;
}
if (mod > 0) {
if (this->m_digits.empty()) {
this->m_digits.push_back(0);
}
this->m_digits[0] += mod;
}
this->regularize<2>();
} else {
this->regularize<0>();
}
}
return *this;
}
::tools::bigint& divide_by_pow10(const ::std::ptrdiff_t exponent) {
this->multiply_by_pow10(-exponent);
return *this;
}
static int compare_3way(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
if (!lhs.m_positive && rhs.m_positive) return -1;
if (lhs.m_positive && !rhs.m_positive) return 1;
return ::tools::bigint::compare_3way_abs(lhs, rhs) * (lhs.m_positive ? 1 : -1);
}
int signum() const {
if (!this->m_positive) return -1;
if (this->m_digits.empty()) return 0;
return 1;
}
::std::size_t size() const {
if (this->m_digits.empty()) return 0;
return LOG10_BASE * (this->m_digits.size() - 1) + ::std::distance(POW10.begin(), ::std::upper_bound(POW10.begin(), POW10.end(), this->m_digits[this->m_digits.size() - 1]));
}
::std::int_fast32_t operator[](const ::std::size_t i) const {
return i < LOG10_BASE * this->m_digits.size() ? this->m_digits[i / LOG10_BASE] / POW10[i % LOG10_BASE] % 10 : 0;
}
private:
template <bool PLUS>
::tools::bigint& internal_add(const ::tools::bigint& other) {
if (this == &other) {
if constexpr (PLUS) {
for (auto& d : this->m_digits) d <<= 1;
this->regularize<1>();
} else {
this->m_digits.clear();
this->m_positive = true;
}
} else {
const bool this_positive = this->m_positive;
if (!this_positive) {
this->negate();
}
this->m_digits.resize(::std::max(this->m_digits.size(), other.m_digits.size()));
if (this_positive == (other.m_positive == PLUS)) {
for (::std::size_t i = 0; i < other.m_digits.size(); ++i) {
this->m_digits[i] += other.m_digits[i];
}
} else {
for (::std::size_t i = 0; i < other.m_digits.size(); ++i) {
this->m_digits[i] -= other.m_digits[i];
}
}
this->regularize<1>();
if (!this_positive) {
this->negate();
}
}
return *this;
}
public:
bigint() : m_positive(true) {
}
bigint(const ::tools::bigint&) = default;
bigint(::tools::bigint&&) = default;
~bigint() = default;
::tools::bigint& operator=(const ::tools::bigint&) = default;
::tools::bigint& operator=(::tools::bigint&&) = default;
template <typename T, typename ::std::enable_if<::std::is_integral_v<T> || ::std::is_same_v<T, ::tools::int128_t> || ::std::is_same_v<T, ::tools::uint128_t>, ::std::nullptr_t>::type = nullptr>
explicit bigint(T n) : m_positive(n >= 0) {
while (n != 0) {
this->m_digits.push_back(n % BASE);
n /= BASE;
}
if (!this->m_positive) {
for (auto& d : this->m_digits) {
d = -d;
}
}
}
explicit bigint(const ::std::string& s) {
assert(!s.empty());
::std::size_t offset;
if (s[0] == '+') {
this->m_positive = true;
offset = 1;
} else if (s[0] == '-') {
this->m_positive = false;
offset = 1;
} else {
this->m_positive = true;
offset = 0;
}
this->m_digits.reserve(::tools::ceil<::std::size_t>(s.size() - offset, LOG10_BASE));
for (::std::size_t i = 0; i < s.size() - offset; i += LOG10_BASE) {
this->m_digits.push_back(0);
for (::std::size_t j = ::std::min(i + LOG10_BASE, s.size() - offset); j --> i;) {
assert('0' <= s[s.size() - 1 - j] && s[s.size() - 1 - j] <= '9');
this->m_digits.back() = this->m_digits.back() * 10 + (s[s.size() - 1 - j] - '0');
}
}
this->regularize<0>();
}
friend bool operator==(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return lhs.m_positive == rhs.m_positive && lhs.m_digits == rhs.m_digits;
}
friend bool operator!=(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return !(lhs == rhs);
}
friend bool operator<(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint::compare_3way(lhs, rhs) < 0;
}
friend bool operator>(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint::compare_3way(lhs, rhs) > 0;
}
friend bool operator<=(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint::compare_3way(lhs, rhs) <= 0;
}
friend bool operator>=(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint::compare_3way(lhs, rhs) >= 0;
}
::tools::bigint operator+() const {
return *this;
}
::tools::bigint operator-() const {
return ::tools::bigint(*this).negate();
}
::tools::bigint& operator+=(const ::tools::bigint& other) {
return this->internal_add<true>(other);
}
::tools::bigint& operator-=(const ::tools::bigint& other) {
return this->internal_add<false>(other);
}
::tools::bigint& operator*=(const ::tools::bigint& other) {
// Constraint derived from atcoder::convolution
assert(this->m_digits.size() + other.m_digits.size() <= ::tools::pow2(25) + 1);
::std::vector<mint1> a1, b1;
::std::vector<mint2> a2, b2;
a1.reserve(this->m_digits.size());
a2.reserve(this->m_digits.size());
b1.reserve(other.m_digits.size());
b2.reserve(other.m_digits.size());
for (const auto a_i : this->m_digits) {
a1.push_back(mint1::raw(a_i));
a2.push_back(mint2::raw(a_i));
}
for (const auto b_i : other.m_digits) {
b1.push_back(mint1::raw(b_i));
b2.push_back(mint2::raw(b_i));
}
const auto c1 = ::atcoder::convolution(a1, b1);
const auto c2 = ::atcoder::convolution(a2, b2);
this->m_digits.clear();
this->m_digits.reserve(c1.size() + 1);
long long carry = 0;
for (::std::size_t i = 0; i < c1.size(); ++i) {
// Since a_i <= 10^4 - 1 and b_i <= 10^4 - 1, c_i <= (10^4 - 1)^2 * min(this->m_digits.size(), other.m_digits.size()) holds.
// In addition, since this->m_digits.size() + other.m_digits.size() <= 2^25 + 1, c_i <= (10^4 - 1)^2 * 2^24 = 1677386072457216 holds eventually.
// 1677386072457216 < 167772161 * 469762049 = 78812994116517889 holds, so we can reconstruct c_i from mod(c_i, 167772161) and mod(c_i, 469762049) by CRT.
long long c_i = ::tools::garner2(c1[i], c2[i]);
c_i += carry;
carry = c_i / BASE;
c_i %= BASE;
this->m_digits.push_back(c_i);
}
if (carry > 0) {
this->m_digits.push_back(carry);
}
this->m_positive = this->m_positive == other.m_positive;
this->regularize<0>();
return *this;
}
friend ::tools::bigint operator+(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint(lhs) += rhs;
}
friend ::tools::bigint operator-(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint(lhs) -= rhs;
}
friend ::tools::bigint operator*(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return ::tools::bigint(lhs) *= rhs;
}
::tools::bigint& operator++() {
return *this += ::tools::bigint(1);
}
::tools::bigint operator++(int) {
::tools::bigint old(*this);
++(*this);
return old;
}
::tools::bigint& operator--() {
return *this -= ::tools::bigint(1);
}
::tools::bigint operator--(int) {
::tools::bigint old(*this);
--(*this);
return old;
}
private:
static const ::tools::bigint& divmod_naive_u64_threshold() {
static const ::tools::bigint threshold((::std::numeric_limits<::std::uint_fast64_t>::max() - (BASE - 1)) / BASE);
return threshold;
}
::std::pair<::tools::bigint, ::tools::bigint> divmod_naive_u64(const ::tools::bigint& other) const {
assert(!other.m_digits.empty());
assert(::tools::bigint::compare_3way_abs(other, divmod_naive_u64_threshold()) <= 0);
::std::uint_fast64_t b = 0;
for (::std::size_t i = other.m_digits.size(); i --> 0;) {
b *= BASE;
b += other.m_digits[i];
}
::tools::bigint Q(*this);
::std::uint_fast64_t r = 0;
for (::std::size_t i = Q.m_digits.size(); i--> 0;) {
r *= BASE;
r += Q.m_digits[i];
Q.m_digits[i] = r / b;
r %= b;
}
Q.m_positive = (this->m_positive == other.m_positive);
Q.regularize<0>();
::tools::bigint R(r);
R.m_positive = (r == 0 || this->m_positive);
return ::std::make_pair(Q, R);
}
static const ::tools::bigint& divmod_naive_u128_threshold() {
static const ::tools::bigint threshold("34028236692093846346337460743176820");
return threshold;
}
::std::pair<::tools::bigint, ::tools::bigint> divmod_naive_u128(const ::tools::bigint& other) const {
assert(!other.m_digits.empty());
assert(::tools::bigint::compare_3way_abs(other, divmod_naive_u128_threshold()) <= 0);
::tools::uint128_t b = 0;
for (::std::size_t i = other.m_digits.size(); i --> 0;) {
b *= BASE;
b += other.m_digits[i];
}
::tools::bigint Q(*this);
::tools::uint128_t r = 0;
for (::std::size_t i = Q.m_digits.size(); i--> 0;) {
r *= BASE;
r += Q.m_digits[i];
Q.m_digits[i] = r / b;
r %= b;
}
Q.m_positive = (this->m_positive == other.m_positive);
Q.regularize<0>();
::tools::bigint R(r);
R.m_positive = (r == 0 || this->m_positive);
return ::std::make_pair(Q, R);
}
// S1の[l1, r1)桁目 * (BASE ** n1) <=> S2の[l2, r2)桁目 * (BASE ** n2)
static int compare_3way_abs(const ::tools::bigint& S1, ::std::size_t l1, ::std::size_t r1, ::std::size_t n1, const ::tools::bigint& S2, ::std::size_t l2, ::std::size_t r2, ::std::size_t n2) {
assert(l1 <= r1);
assert(l2 <= r2);
::tools::chmin(l1, S1.m_digits.size());
::tools::chmin(r1, S1.m_digits.size());
::tools::chmin(l2, S2.m_digits.size());
::tools::chmin(r2, S2.m_digits.size());
const auto n_min = ::std::min(n1, n2);
n1 -= n_min;
n2 -= n_min;
if (const auto comp = ::tools::bigint::compare_3way(r1 - l1 + n1, r2 - l2 + n2); comp != 0) {
return comp;
}
if (n1 > 0) {
const auto m2 = r2 - (r1 - l1);
for (::std::size_t i1 = r1, i2 = r2; --i1, i2 --> m2;) {
if (const auto comp = ::tools::bigint::compare_3way(S1.m_digits[i1], S2.m_digits[i2]); comp != 0) {
return comp;
}
}
for (::std::size_t i2 = m2; i2 --> l2;) {
if (0 < S2.m_digits[i2]) {
return -1;
}
}
} else if (n2 > 0) {
const auto m1 = r1 - (r2 - l2);
for (::std::size_t i1 = r1, i2 = r2; --i1, i2 --> l2;) {
if (const auto comp = ::tools::bigint::compare_3way(S1.m_digits[i1], S2.m_digits[i2]); comp != 0) {
return comp;
}
}
for (::std::size_t i1 = m1; i1 --> l1;) {
if (S1.m_digits[i1] > 0) {
return 1;
}
}
} else {
for (::std::size_t i1 = r1, i2 = r2; --i1, i2 --> l2;) {
if (const auto comp = ::tools::bigint::compare_3way(S1.m_digits[i1], S2.m_digits[i2]); comp != 0) {
return comp;
}
}
}
return 0;
}
// *thisの[l, r)桁目
::tools::bigint slice(::std::size_t l, ::std::size_t r) const {
assert(this->m_positive);
assert(l <= r);
::tools::chmin(l, this->m_digits.size());
::tools::chmin(r, this->m_digits.size());
::tools::bigint S;
S.m_digits.reserve(r - l);
::std::copy(this->m_digits.begin() + l, this->m_digits.begin() + r, ::std::back_inserter(S.m_digits));
return S.regularize<0>();
}
// *this * (BASE ** n)
::tools::bigint lshift(const int n) const {
assert(this->m_positive);
if (n == 0) return *this;
if (this->m_digits.empty()) return *this;
::tools::bigint S;
S.m_digits.reserve(n + this->m_digits.size());
::std::fill_n(::std::back_inserter(S.m_digits), n, 0);
::std::copy(this->m_digits.begin(), this->m_digits.end(), ::std::back_inserter(S.m_digits));
return S;
}
// *this / (BASE ** n)
::tools::bigint rshift(const ::std::size_t n) const {
assert(this->m_positive);
if (this->m_digits.size() <= n) return ::tools::bigint{};
::tools::bigint S;
S.m_digits.reserve(this->m_digits.size() - n);
::std::copy(this->m_digits.begin() + n, this->m_digits.end(), ::std::back_inserter(S.m_digits));
return S;
}
// *this * (BASE ** (r - l)) + otherの[l, r)桁目
::tools::bigint concat(const ::tools::bigint& other, ::std::size_t l, ::std::size_t r) const {
assert(this->m_positive);
assert(other.m_positive);
assert(l < r);
if (this->m_digits.empty()) return other.slice(l, r);
const auto n = r - l;
::tools::chmin(l, other.m_digits.size());
::tools::chmin(r, other.m_digits.size());
::tools::bigint S;
S.m_digits.reserve(this->m_digits.size() + n);
::std::copy(other.m_digits.begin() + l, other.m_digits.begin() + r, ::std::back_inserter(S.m_digits));
::std::fill_n(::std::back_inserter(S.m_digits), n - (r - l), 0);
::std::copy(this->m_digits.begin(), this->m_digits.end(), ::std::back_inserter(S.m_digits));
return S;
}
::std::pair<::tools::bigint, ::tools::bigint> divmod_3n_2n(const ::tools::bigint& other, const ::std::size_t n) const {
assert(this->m_positive);
assert(this->m_digits.size() <= n * 3);
assert(other.m_positive);
assert(other.m_digits.size() == n * 2);
assert(BASE <= other.m_digits.back() * 2);
assert(compare_3way_abs(*this, 0, n * 3, 0, other, 0, n * 2, n) < 0);
::tools::bigint Q_hat, S, D;
if (compare_3way_abs(*this, n * 2, n * 3, 0, other, n, n * 2, 0) < 0) {
::std::tie(Q_hat, S) = this->slice(n, n * 3).divmod_2n_n(other.slice(n, n * 2), n);
D = other.slice(0, n);
D *= Q_hat;
} else {
Q_hat.m_digits.assign(n, BASE - 1);
S = this->slice(n, n * 3);
S += other.slice(n, n * 2);
S -= other.slice(n, n * 2).lshift(n);
D = other.slice(0, n).lshift(n);
D -= other.slice(0, n);
}
auto R_hat = S.concat(*this, 0, n);
R_hat -= D;
while (!R_hat.m_positive) {
R_hat += other;
--Q_hat;
}
return ::std::make_pair(Q_hat, R_hat);
}
::std::pair<::tools::bigint, ::tools::bigint> divmod_4n_2n(const ::tools::bigint& other, const ::std::size_t n) const {
assert(this->m_positive);
assert(this->m_digits.size() <= n * 4);
assert(other.m_positive);
assert(other.m_digits.size() == n * 2);
assert(BASE <= other.m_digits.back() * 2);
assert(compare_3way_abs(*this, 0, n * 4, 0, other, 0, n * 2, n * 2) < 0);
const auto [Q1, S] = this->slice(n, n * 4).divmod_3n_2n(other, n);
const auto [Q0, R] = S.concat(*this, 0, n).divmod_3n_2n(other, n);
return ::std::make_pair(Q1.concat(Q0, 0, n), R);
}
::std::pair<::tools::bigint, ::tools::bigint> divmod_2n_n(const ::tools::bigint& other, const ::std::size_t n) const {
assert(this->m_positive);
assert(this->m_digits.size() <= n * 2);
assert(other.m_positive);
assert(other.m_digits.size() == n);
assert(BASE <= other.m_digits.back() * 2);
if (other.m_digits.size() <= 3) {
return this->divmod_naive_u64(other);
}
if (other.m_digits.size() <= 8) {
return this->divmod_naive_u128(other);
}
assert(n % 2 == 0);
return this->divmod_4n_2n(other, n / 2);
}
public:
::std::pair<::tools::bigint, ::tools::bigint> divmod(const ::tools::bigint& other) const {
assert(!other.m_digits.empty());
if (::tools::bigint::compare_3way_abs(*this, other) < 0) {
return ::std::make_pair(::tools::bigint{}, *this);
}
if (::tools::bigint::compare_3way_abs(other, divmod_naive_u64_threshold()) <= 0) {
return this->divmod_naive_u64(other);
}
if (::tools::bigint::compare_3way_abs(other, divmod_naive_u128_threshold()) <= 0) {
return this->divmod_naive_u128(other);
}
if (!this->m_positive || !other.m_positive) {
auto [Q, R] = ::tools::abs(*this).divmod(::tools::abs(other));
Q.m_positive = Q.m_digits.empty() || (this->m_positive == other.m_positive);
R.m_positive = R.m_digits.empty() || this->m_positive;
return ::std::make_pair(Q, R);
}
const ::std::size_t DIV_LIMIT = 8;
const auto s = other.m_digits.size();
const auto m = ::tools::pow2(::tools::floor_log2(s / DIV_LIMIT) + 1);
const auto n = ::tools::ceil(s, m) * m;
const auto sigma1 = n - s;
auto sigma2 = ::tools::pow2(::tools::floor_log2(BASE / (other.m_digits.back() + 1)));
auto B = other.lshift(sigma1);
for (auto& B_i : B.m_digits) B_i *= sigma2;
B.regularize<2>();
assert(B.m_digits.size() == n);
while (B.m_digits.back() * 2 < BASE) {
sigma2 *= 2;
B += B;
assert(B.m_digits.size() == n);
}
auto A = this->lshift(sigma1);
for (auto& A_i : A.m_digits) A_i *= sigma2;
A.regularize<2>();
const auto t = ::std::max<::std::size_t>(2, ::tools::ceil(A.m_digits.size() + 1, n));
::tools::bigint Q, Q_i, R_i;
Q.m_digits.resize(n * (t - 1));
auto Z = A.slice(n * (t - 2), n * t);
::std::tie(Q_i, R_i) = Z.divmod_2n_n(B, n);
::std::copy(Q_i.m_digits.begin(), Q_i.m_digits.end(), Q.m_digits.begin() + n * (t - 2));
for (::std::size_t i = t - 2; i --> 0;) {
Z = R_i.concat(A, n * i, n * (i + 1));
::std::tie(Q_i, R_i) = Z.divmod_2n_n(B, n);
::std::copy(Q_i.m_digits.begin(), Q_i.m_digits.end(), Q.m_digits.begin() + n * i);
}
return ::std::make_pair(Q.regularize<0>(), R_i.divmod_naive_u64(::tools::bigint(sigma2)).first.rshift(sigma1));
}
::tools::bigint& operator/=(const ::tools::bigint& other) {
return *this = *this / other;
}
friend ::tools::bigint operator/(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return lhs.divmod(rhs).first;
}
::tools::bigint& operator%=(const ::tools::bigint& other) {
return *this = *this % other;
}
friend ::tools::bigint operator%(const ::tools::bigint& lhs, const ::tools::bigint& rhs) {
return lhs.divmod(rhs).second;
}
template <typename T, ::std::enable_if_t<::std::is_integral_v<T>, ::std::nullptr_t> = nullptr>
explicit operator T() const {
assert(::tools::bigint(::std::numeric_limits<T>::min()) <= *this && *this <= ::tools::bigint(::std::numeric_limits<T>::max()));
T result = 0;
for (::std::size_t i = this->m_digits.size(); i --> 0;) {
result = result * BASE + this->m_digits[i] * (this->m_positive ? 1 : -1);
}
return result;
}
explicit operator bool() const {
return !this->m_digits.empty();
}
explicit operator ::tools::int128_t() const {
assert(::tools::bigint(::std::numeric_limits<::tools::int128_t>::min()) <= *this && *this <= ::tools::bigint(::std::numeric_limits<::tools::int128_t>::max()));
::tools::int128_t result = 0;
for (::std::size_t i = this->m_digits.size(); i --> 0;) {
result = result * BASE + this->m_digits[i] * (this->m_positive ? 1 : -1);
}
return result;
}
explicit operator ::tools::uint128_t() const {
assert(::tools::bigint(0) <= *this && *this <= ::tools::bigint(::std::numeric_limits<::tools::uint128_t>::max()));
::tools::uint128_t result = 0;
for (::std::size_t i = this->m_digits.size(); i --> 0;) {
result = result * BASE + this->m_digits[i];
}
return result;
}
explicit operator double() const {
long double result = 0.0;
const ::std::size_t precision = this->size();
for (::std::size_t i = 0; i < ::std::numeric_limits<long double>::digits10; ++i) {
result = result * 10.0L + (precision >= i + 1 ? (*this)[precision - 1 - i] : 0) * this->signum();
}
result *= ::std::pow(10.0L, static_cast<long double>(precision) - static_cast<long double>(::std::numeric_limits<long double>::digits10));
return static_cast<double>(result);
}
friend ::std::istream& operator>>(::std::istream& is, ::tools::bigint& self) {
::std::string s;
is >> s;
self = ::tools::bigint(s);
return is;
}
friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::bigint& self) {
if (!self.m_positive) {
os << '-';
}
if (self.m_digits.empty()) {
return os << '0';
}
os << self.m_digits.back();
for (::std::size_t i = 1; i < self.m_digits.size(); ++i) {
os << ::std::setw(LOG10_BASE) << ::std::setfill('0') << self.m_digits[self.m_digits.size() - 1 - i];
}
return os;
}
friend ::tools::bigint abs(::tools::bigint x);
};
inline ::tools::bigint abs(::tools::bigint x) {
if (!x.m_positive) x.negate();
return x;
}
template <>
::tools::bigint gcd<::tools::bigint, ::tools::bigint>(::tools::bigint x, ::tools::bigint y) {
if (x.signum() < 0) x.negate();
if (y.signum() < 0) y.negate();
while (y.signum() != 0) {
x %= y;
::std::swap(x, y);
}
return x;
}
}
#line 1 "tools/bigdecimal.hpp"
#line 1 "tools/signum.hpp"
#line 5 "tools/signum.hpp"
namespace tools {
template <typename T>
constexpr int signum(const T x) noexcept {
if constexpr (::tools::is_unsigned_v<T>) {
return T(0) < x;
} else {
return (T(0) < x) - (x < T(0));
}
}
}
#line 1 "tools/rounding_mode.hpp"
namespace tools {
enum class rounding_mode {
ceiling,
down,
floor,
half_down,
half_even,
half_up,
up
};
}
#line 17 "tools/bigdecimal.hpp"
namespace tools {
class bigdecimal {
private:
// *this := this->m_unscaled_value * (10 ** -this->m_scale)
::tools::bigint m_unscaled_value;
::std::ptrdiff_t m_scale;
public:
const ::tools::bigint& unscaled_value() const {
return this->m_unscaled_value;
}
::std::size_t precision() const {
return this->m_unscaled_value.size();
}
::std::ptrdiff_t scale() const {
return this->m_scale;
}
int signum() const {
return this->m_unscaled_value.signum();
}
::tools::bigdecimal& negate() {
this->m_unscaled_value.negate();
return *this;
}
::tools::bigdecimal& multiply_by_pow10(const ::std::ptrdiff_t n) {
this->m_scale -= n;
return *this;
}
::tools::bigdecimal& divide_by_pow10(const ::std::ptrdiff_t n) {
return this->multiply_by_pow10(-n);
}
::tools::bigdecimal& set_scale(const ::std::ptrdiff_t s) {
this->m_unscaled_value.multiply_by_pow10(s - this->m_scale);
this->m_scale = s;
return *this;
}
static int compare_3way(const ::tools::bigdecimal& x, const ::tools::bigdecimal& y) {
if (const auto comp = ::tools::signum(x.m_unscaled_value.signum() - y.m_unscaled_value.signum()); comp != 0) {
return comp;
}
return [&]() {
::tools::bigdecimal abs_x(x);
if (abs_x.signum() < 0) abs_x.negate();
abs_x.set_scale(::std::max(x.m_scale, y.m_scale));
::tools::bigdecimal abs_y(y);
if (abs_y.signum() < 0) abs_y.negate();
abs_y.set_scale(::std::max(x.m_scale, y.m_scale));
return ::tools::bigint::compare_3way(abs_x.m_unscaled_value, abs_y.m_unscaled_value);
}() * x.m_unscaled_value.signum();
}
bigdecimal() : m_unscaled_value(0), m_scale(0) {
}
bigdecimal(const ::tools::bigdecimal&) = default;
bigdecimal(::tools::bigdecimal&&) = default;
~bigdecimal() = default;
::tools::bigdecimal& operator=(const ::tools::bigdecimal&) = default;
::tools::bigdecimal& operator=(::tools::bigdecimal&&) = default;
explicit bigdecimal(const long long n) : m_unscaled_value(n), m_scale(0) {
}
explicit bigdecimal(const ::tools::bigint& n) : m_unscaled_value(n), m_scale(0) {
}
explicit bigdecimal(::std::string s) {
if (const auto pos = s.find('.'); pos != ::std::string::npos) {
this->m_scale = s.size() - pos - 1;
s.erase(pos, 1);
} else {
this->m_scale = 0;
}
this->m_unscaled_value = ::tools::bigint(s);
}
friend bool operator==(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) == 0;
}
friend bool operator!=(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) != 0;
}
friend bool operator<(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) < 0;
}
friend bool operator>(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) > 0;
}
friend bool operator<=(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) <= 0;
}
friend bool operator>=(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal::compare_3way(lhs, rhs) >= 0;
}
::tools::bigdecimal operator+() const {
return *this;
}
::tools::bigdecimal operator-() const {
return ::tools::bigdecimal(*this).negate();
}
::tools::bigdecimal& operator+=(::tools::bigdecimal other) {
const ::std::size_t scale = ::std::max(this->m_scale, other.m_scale);
this->set_scale(scale);
other.set_scale(scale);
this->m_unscaled_value += other.m_unscaled_value;
return *this;
}
::tools::bigdecimal& operator-=(::tools::bigdecimal other) {
const ::std::size_t scale = ::std::max(this->m_scale, other.m_scale);
this->set_scale(scale);
other.set_scale(scale);
this->m_unscaled_value -= other.m_unscaled_value;
return *this;
}
::tools::bigdecimal& operator*=(const ::tools::bigdecimal& other) {
this->m_unscaled_value *= other.m_unscaled_value;
this->m_scale += other.m_scale;
return *this;
}
::tools::bigdecimal& divide(const ::tools::bigdecimal& other, const ::std::ptrdiff_t scale, const ::tools::rounding_mode rounding_mode) {
assert(other.signum() != 0);
static const auto compare_3way_abs = [](::tools::bigdecimal& x, ::tools::bigdecimal& y) {
const bool x_positive = x.signum() >= 0;
const bool y_positive = y.signum() >= 0;
if (!x_positive) x.negate();
if (!y_positive) y.negate();
const int result = ::tools::bigdecimal::compare_3way(x, y);
if (!x_positive) x.negate();
if (!y_positive) y.negate();
return result;
};
::tools::bigdecimal old_this(*this);
this->m_unscaled_value.multiply_by_pow10(scale - (this->m_scale - other.m_scale));
this->m_unscaled_value /= other.m_unscaled_value;
this->m_scale = scale;
if ([&]() {
if (rounding_mode == ::tools::rounding_mode::down) {
return false;
}
if (rounding_mode == ::tools::rounding_mode::ceiling || rounding_mode == ::tools::rounding_mode::floor || rounding_mode == ::tools::rounding_mode::up) {
if ((rounding_mode == ::tools::rounding_mode::ceiling && old_this.signum() * other.signum() > 0)
|| (rounding_mode == ::tools::rounding_mode::floor && old_this.signum() * other.signum() < 0)
|| rounding_mode == ::tools::rounding_mode::up) {
::tools::bigdecimal d(*this);
d *= other;
return compare_3way_abs(old_this, d) > 0;
} else {
return false;
}
}
::tools::bigdecimal d(*this);
d += ::tools::bigdecimal(5 * old_this.signum() * other.signum()).divide_by_pow10(scale + 1);
d *= other;
const int comp = compare_3way_abs(old_this, d);
if (rounding_mode == ::tools::rounding_mode::half_down) {
return comp > 0;
}
if (rounding_mode == ::tools::rounding_mode::half_up) {
return comp >= 0;
}
return comp > 0 || (comp == 0 && this->m_unscaled_value[0] % 2 != 0);
}()) {
this->m_scale = scale;
this->m_unscaled_value += ::tools::bigint(old_this.signum() * other.signum());
}
return *this;
}
::tools::bigdecimal& divide(const ::tools::bigdecimal& other, const ::std::ptrdiff_t scale) {
return this->divide(other, scale, ::tools::rounding_mode::half_even);
}
::tools::bigdecimal& operator/=(const ::tools::bigdecimal& other) {
return this->divide(other, this->m_scale - other.m_scale);
}
friend ::tools::bigdecimal operator+(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal(lhs) += rhs;
}
friend ::tools::bigdecimal operator-(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal(lhs) -= rhs;
}
friend ::tools::bigdecimal operator*(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal(lhs) *= rhs;
}
::tools::bigdecimal divide_and_copy(const ::tools::bigdecimal& other, const ::std::ptrdiff_t scale, const ::tools::rounding_mode rounding_mode) const {
return ::tools::bigdecimal(*this).divide(other, scale, rounding_mode);
}
::tools::bigdecimal divide_and_copy(const ::tools::bigdecimal& other, const ::std::ptrdiff_t scale) const {
return ::tools::bigdecimal(*this).divide(other, scale);
}
friend ::tools::bigdecimal operator/(const ::tools::bigdecimal& lhs, const ::tools::bigdecimal& rhs) {
return ::tools::bigdecimal(lhs) /= rhs;
}
template <typename T, ::std::enable_if_t<::std::is_integral_v<T>, ::std::nullptr_t> = nullptr>
explicit operator T() const {
auto x = *this;
x.set_scale(0);
return static_cast<T>(x.m_unscaled_value);
}
explicit operator double() const {
long double result = 0.0;
const ::std::size_t precision = this->precision();
for (::std::size_t i = 0; i < ::std::numeric_limits<long double>::digits10; ++i) {
result = result * 10.0L + (precision >= i + 1 ? this->m_unscaled_value[precision - 1 - i] : 0) * this->signum();
}
result *= ::std::pow(10.0L, static_cast<long double>(precision) - static_cast<long double>(this->m_scale) - static_cast<long double>(::std::numeric_limits<long double>::digits10));
return static_cast<double>(result);
}
friend ::std::istream& operator>>(::std::istream& is, ::tools::bigdecimal& self) {
::std::string s;
is >> s;
self = ::tools::bigdecimal(s);
return is;
}
friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::bigdecimal& self) {
if (self.signum() == 0 && self.m_scale <= 0) {
return os << '0';
}
if (self.signum() < 0) {
os << '-';
}
for (auto i = ::std::max(::std::ssize(self.m_unscaled_value) - 1, self.m_scale); i >= ::std::min<::std::ptrdiff_t>(0, self.m_scale); --i) {
if (i == self.m_scale - 1) {
os << '.';
}
os << (0 <= i && i < ::std::ssize(self.m_unscaled_value) ? self.m_unscaled_value[i] : 0);
}
return os;
}
};
inline ::tools::bigdecimal abs(::tools::bigdecimal x) {
if (x.signum() < 0) x.negate();
return x;
}
}
#line 1 "tools/is_rational.hpp"
#line 5 "tools/is_rational.hpp"
namespace tools {
template <typename T>
struct is_rational : std::false_type {};
template <typename T>
inline constexpr bool is_rational_v = ::tools::is_rational<T>::value;
}
#line 17 "tools/rational.hpp"
namespace tools {
class rational {
private:
::tools::bigint m_numerator;
::tools::bigint m_denominator;
::tools::rational& regularize() {
if (this->m_denominator.signum() < 0) {
this->m_numerator.negate();
this->m_denominator.negate();
}
if (this->m_numerator.signum() == 0) {
this->m_denominator = ::tools::bigint(1);
} else {
const ::tools::bigint gcd = ::tools::gcd(this->m_numerator, this->m_denominator);
this->m_numerator /= gcd;
this->m_denominator /= gcd;
}
return *this;
}
public:
int signum() const {
return this->m_numerator.signum();
}
::tools::rational& negate() {
this->m_numerator.negate();
return *this;
}
static int compare_3way(const ::tools::rational& lhs, const ::tools::rational& rhs) {
if (const auto comp = ::tools::signum(lhs.signum() - rhs.signum()); comp != 0) {
return comp;
}
return ::tools::bigint::compare_3way(lhs.m_numerator * rhs.m_denominator, rhs.m_numerator * lhs.m_denominator);
}
rational() : m_numerator(0), m_denominator(1) {
}
rational(const ::tools::rational&) = default;
rational(::tools::rational&&) = default;
~rational() = default;
::tools::rational& operator=(const ::tools::rational&) = default;
::tools::rational& operator=(::tools::rational&&) = default;
explicit rational(const long long n) : m_numerator(n), m_denominator(1) {
}
explicit rational(const ::tools::bigint& n) : m_numerator(n), m_denominator(1) {
}
explicit rational(const ::tools::bigdecimal& d)
: m_numerator(::tools::bigint(1).multiply_by_pow10(::std::max<::std::ptrdiff_t>(0, -d.scale())) *= d.unscaled_value()),
m_denominator(::tools::bigint(1).multiply_by_pow10(::std::max<::std::ptrdiff_t>(0, d.scale()))) {
this->regularize();
}
rational(const long long numerator, const long long denominator)
: m_numerator(numerator), m_denominator(denominator) {
assert(denominator != 0);
this->regularize();
}
rational(const ::tools::bigint& numerator, const ::tools::bigint& denominator)
: m_numerator(numerator), m_denominator(denominator) {
assert(this->m_denominator.signum() != 0);
this->regularize();
}
const ::tools::bigint& numerator() const {
return this->m_numerator;
}
const ::tools::bigint& denominator() const {
return this->m_denominator;
}
friend bool operator==(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return lhs.m_numerator == rhs.m_numerator && lhs.m_denominator == rhs.m_denominator;
}
friend bool operator!=(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return !(lhs == rhs);
}
friend bool operator<(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational::compare_3way(lhs, rhs) < 0;
}
friend bool operator>(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational::compare_3way(lhs, rhs) > 0;
}
friend bool operator<=(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational::compare_3way(lhs, rhs) <= 0;
}
friend bool operator>=(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational::compare_3way(lhs, rhs) >= 0;
}
::tools::rational operator+() const {
return *this;
}
::tools::rational operator-() const {
return ::tools::rational(*this).negate();
}
::tools::rational& operator+=(const ::tools::rational& other) {
this->m_numerator *= other.m_denominator;
this->m_numerator += other.m_numerator * this->m_denominator;
this->m_denominator *= other.m_denominator;
return this->regularize();
}
friend ::tools::rational operator+(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational(lhs) += rhs;
}
::tools::rational& operator-=(const ::tools::rational& other) {
this->m_numerator *= other.m_denominator;
this->m_numerator -= other.m_numerator * this->m_denominator;
this->m_denominator *= other.m_denominator;
return this->regularize();
}
friend ::tools::rational operator-(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational(lhs) -= rhs;
}
::tools::rational& operator*=(const ::tools::rational& other) {
this->m_numerator *= other.m_numerator;
this->m_denominator *= other.m_denominator;
return this->regularize();
}
friend ::tools::rational operator*(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational(lhs) *= rhs;
}
::tools::rational& operator/=(const ::tools::rational& other) {
assert(other.signum() != 0);
this->m_numerator *= other.m_denominator;
this->m_denominator *= other.m_numerator;
return this->regularize();
}
friend ::tools::rational operator/(const ::tools::rational& lhs, const ::tools::rational& rhs) {
return ::tools::rational(lhs) /= rhs;
}
template <typename T, ::std::enable_if_t<::std::is_integral_v<T>, ::std::nullptr_t> = nullptr>
explicit operator T() const {
return static_cast<T>(this->m_numerator / this->m_denominator);
}
explicit operator double() const {
::tools::bigint unscaled_value(this->m_numerator);
unscaled_value.multiply_by_pow10((::std::numeric_limits<double>::digits10 + 2) - (::std::ssize(this->m_numerator) - ::std::ssize(this->m_denominator)));
unscaled_value /= this->m_denominator;
::tools::bigdecimal result(unscaled_value);
result.divide_by_pow10((::std::numeric_limits<double>::digits10 + 2) - (::std::ssize(this->m_numerator) - ::std::ssize(this->m_denominator)));
return static_cast<double>(result);
}
friend ::std::istream& operator>>(::std::istream& is, ::tools::rational& self) {
::tools::bigdecimal value;
is >> value;
self = ::tools::rational(value);
return is;
}
friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::rational& self) {
return os << '(' << self.m_numerator << '/' << self.m_denominator << ')';
}
};
template <>
struct is_rational<::tools::rational> : ::std::true_type {};
inline ::tools::rational abs(::tools::rational x) {
if (x.signum() < 0) x.negate();
return x;
}
}
#line 5 "tests/rational/plus.test.cpp"
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
tools::rational A, B;
std::cin >> A >> B;
std::cout << (A + B).numerator() << '\n';
return 0;
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | 00_sample_00.in |
AC |
5 ms | 4 MB |
| g++ | 00_sample_01.in |
AC |
5 ms | 4 MB |
| g++ | 00_sample_02.in |
AC |
5 ms | 4 MB |
| g++ | 00_sample_03.in |
AC |
5 ms | 4 MB |
| g++ | 01_minimum_00.in |
AC |
5 ms | 4 MB |
| g++ | 01_minimum_01.in |
AC |
4 ms | 4 MB |
| g++ | 01_minimum_02.in |
AC |
4 ms | 4 MB |
| g++ | 01_minimum_03.in |
AC |
4 ms | 4 MB |
| g++ | 02_random_00.in |
AC |
5 ms | 4 MB |
| g++ | 02_random_01.in |
AC |
5 ms | 4 MB |
| g++ | 02_random_02.in |
AC |
5 ms | 4 MB |
| g++ | 02_random_03.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_00.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_01.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_02.in |
AC |
4 ms | 4 MB |
| g++ | 03_random_03.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_04.in |
AC |
4 ms | 4 MB |
| g++ | 03_random_05.in |
AC |
4 ms | 4 MB |
| g++ | 03_random_06.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_07.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_08.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_09.in |
AC |
5 ms | 4 MB |
| g++ | 03_random_10.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_00.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_01.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_02.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_03.in |
AC |
5 ms | 4 MB |
| g++ | 04_large_04.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_05.in |
AC |
4 ms | 4 MB |
| g++ | 04_large_06.in |
AC |
4 ms | 4 MB |
| g++ | 05_maximum_00.in |
AC |
8 ms | 4 MB |
| g++ | 05_maximum_01.in |
AC |
8 ms | 5 MB |
| g++ | 05_maximum_02.in |
AC |
10 ms | 5 MB |
| g++ | 05_maximum_03.in |
AC |
10 ms | 5 MB |
| g++ | 05_maximum_04.in |
AC |
8 ms | 4 MB |
| g++ | 05_maximum_05.in |
AC |
8 ms | 4 MB |
| g++ | 05_maximum_06.in |
AC |
10 ms | 5 MB |
| g++ | 05_maximum_07.in |
AC |
10 ms | 5 MB |
| g++ | 06_corner_00.in |
AC |
5 ms | 4 MB |
| g++ | 06_corner_01.in |
AC |
5 ms | 4 MB |
| g++ | 06_corner_02.in |
AC |
4 ms | 4 MB |
| g++ | 06_corner_03.in |
AC |
4 ms | 4 MB |
| g++ | 07_maximum_corner_00.in |
AC |
8 ms | 4 MB |
| g++ | 07_maximum_corner_01.in |
AC |
8 ms | 4 MB |
| g++ | 07_maximum_corner_02.in |
AC |
9 ms | 5 MB |
| g++ | 07_maximum_corner_03.in |
AC |
9 ms | 5 MB |
| g++ | 07_maximum_corner_04.in |
AC |
8 ms | 5 MB |
| g++ | 07_maximum_corner_05.in |
AC |
8 ms | 5 MB |
| g++ | 07_maximum_corner_06.in |
AC |
9 ms | 5 MB |
| g++ | 07_maximum_corner_07.in |
AC |
9 ms | 5 MB |