結果
| 問題 | No.1803 Remainder of Sum |
| コンテスト | |
| ユーザー |
 miscalc
|
| 提出日時 | 2026-08-04 13:22:24 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| + 415µs | |
| コード長 | 27,471 bytes |
| 記録 | |
| コンパイル時間 | 2,711 ms |
| コンパイル使用メモリ | 353,084 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-08-04 13:22:55 |
| 合計ジャッジ時間 | 4,826 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 8 |
ソースコード
#define INF 4'000'000'000'000'000'037LL
#include <bits/stdc++.h>
using namespace std;
namespace {
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using tlll = tuple<ll, ll, ll>;
#define vc vector
template <class T>
using vvc = vc<vc<T>>;
using vpll = vc<pll>;
using vtlll = vc<tlll>;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
#define cauto const auto
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep2(i, l, r) for (ll i = ll(l), rrrrr = ll(r); i < rrrrr; i++)
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi1(i, n) for (int i = 0, nnnnn = int(n); i < nnnnn; i++)
#define repi(...) overload4(__VA_ARGS__, repi3, repi2, repi1)(__VA_ARGS__)
#define fec(...) for (cauto &__VA_ARGS__)
template <class T>
constexpr bool is_integral_ext = is_integral_v<T> || is_same_v<T, i128> || is_same_v<T, u128>;
template <class T>
constexpr bool is_signed_ext = is_signed_v<T> || is_same_v<T, i128>;
template <class T>
constexpr bool is_unsigned_ext = is_unsigned_v<T> || is_same_v<T, u128>;
template <class T = ll, class U, class V, typename = enable_if_t<is_integral_ext<U> && is_integral_ext<V>>>
inline constexpr T divfloor(U a, V b) { return T(a) / T(b) - (T(a) % T(b) && (T(a) ^ T(b)) < 0); }
template <class T = ll, class U, class V, typename = enable_if_t<is_integral_ext<U> && is_integral_ext<V>>>
inline constexpr T safemod(U a, V b) { return T(a) - T(b) * divfloor<T>(a, b); }
template <class T = ll, class U, class V>
constexpr T ipow(U a, V b)
{
assert(b >= 0);
if (b == 0)
return 1;
if (a == 0 || a == 1)
return a;
if (a < 0 && a == -1)
return b & 1 ? -1 : 1;
T res = 1, tmp = a;
while (true)
{
if (b & 1)
res *= tmp;
b >>= 1;
if (b == 0)
break;
tmp *= tmp;
}
return res;
}
template <class T = ll, class A, class B, class M>
T mul_limited(A a, B b, M m)
{
assert(a >= 0 && b >= 0 && m >= 0);
if (b == 0)
return 0;
return T(a) > T(m) / T(b) ? T(m) : T(a) * T(b);
}
template <class T = ll, class A, class B>
T mul_limited(A a, B b) { return mul_limited<T>(a, b, INF); }
template <class T = ll, class A, class B, class M>
T pow_limited(A a, B b, M m)
{
assert(a >= 0 && b >= 0 && m >= 0);
if (a <= 1 || b == 0)
return min(ipow<T>(a, b), T(m));
T res = 1, tmp = a;
while (true)
{
if (b & 1)
{
if (res > T(m) / tmp)
return m;
res *= tmp;
}
b >>= 1;
if (b == 0)
break;
if (tmp > T(m) / tmp)
return m;
tmp *= tmp;
}
return res;
}
template <class T = ll, class A, class B>
T pow_limited(A a, B b) { return pow_limited<T>(a, b, INF); }
#define ALL(a) (a).begin(), (a).end()
template <class T = ll, class V>
inline T SZ(const V &x) { return x.size(); }
#define eb emplace_back
template <class T, size_t d, size_t i = 0, class V>
auto dvec(const V (&sz)[d], const T &init)
{
if constexpr (i < d)
return vc(sz[i], dvec<T, d, i + 1>(sz, init));
else
return init;
}
template <class T, class U>
vc<T> permuted(const vc<T> &a, const vc<U> &p)
{
const int n = p.size();
vc<T> res(n);
repi(i, n)
{
assert(0 <= p[i] && p[i] < U(a.size()));
res[i] = a[p[i]];
}
return res;
}
template <class T, class U, class... Ts>
vc<T> permuted(const vc<T> &p, const vc<U> &q, const vc<Ts> &...rs)
{
return permuted(permuted(p, q), rs...);
}
#if __cplusplus < 202002L
#else
#endif
template <class V>
void unique(V &v) { v.erase(std::unique(ALL(v)), v.end()); }
template <class V, class U>
void rotate(V &v, U k)
{
const U n = v.size();
k = (k % n + n) % n;
std::rotate(v.begin(), v.begin() + k, v.end());
}
template <class T>
vvc<T> top(const vvc<T> &a)
{
if (a.empty())
return {};
const int n = a.size(), m = a[0].size();
vvc<T> b(m, vc<T>(n));
repi(i, n)
{
assert(SZ<int>(a[i]) == m);
repi(j, m) b[j][i] = a[i][j];
}
return b;
}
template <class T, class = void>
struct has_e0 : false_type {};
template <class T>
struct has_e0<T, void_t<decltype(T::e0())>> : true_type {};
template <class T>
inline constexpr bool has_e0_v = has_e0<T>::value;
const vpll DRULgrid = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const vpll DRULplane = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
template <class T>
struct is_random_access_iterator
{
static constexpr bool value = is_same_v<
typename iterator_traits<T>::iterator_category,
random_access_iterator_tag
>;
};
template <class T>
constexpr bool is_random_access_iterator_v = is_random_access_iterator<T>::value;
#if __cplusplus < 202002L
namespace internal
{
};
#else
#endif
template <class T>
inline constexpr ull MASK(T k) { return (1ULL << k) - 1ULL; }
#if __cplusplus < 202002L
inline constexpr ull countr_zero(ull x) { assert(x != 0); return __builtin_ctzll(x); }
#else
inline constexpr ll bit_width(ll x) { return std::bit_width((ull)x); }
inline constexpr ll bit_floor(ll x) { return std::bit_floor((ull)x); }
inline constexpr ll bit_ceil(ll x) { return std::bit_ceil((ull)x); }
inline constexpr ll countr_zero(ll x) { assert(x != 0); return std::countr_zero((ull)x); }
inline constexpr ll popcount(ll x) { return std::popcount((ull)x); }
inline constexpr bool has_single_bit(ll x) { return std::has_single_bit((ull)x); }
#endif
#define dump(...)
#define local(...)
#define oj(...) __VA_ARGS__
template <class T, class Sequence>
vc<T> content(queue<T, Sequence> que)
{
vc<T> res;
while (!que.empty())
{
res.eb(que.front());
que.pop();
}
return res;
}
template <class T, class Sequence, class Compare>
vc<T> content(priority_queue<T, Sequence, Compare> pque)
{
vc<T> res;
while (!pque.empty())
{
res.eb(pque.top());
pque.pop();
}
return res;
}
template <class T>
auto content(const T &obj) { return obj.content(); }
namespace fastio {
static constexpr uint32_t SIZ = 1 << 17;
char ibuf[SIZ];
char obuf[SIZ];
char out[100];
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SIZ - pir + pil, stdin);
pil = 0;
if (pir < SIZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
template <typename T>
void rd1_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
pil--;
if constexpr (is_signed<T>::value || is_same_v<T, i128>)
{
if (minus) x = -x;
}
}
void rd1(ll &x) { rd1_integer(x); }
void rd1(uint &x) { rd1_integer(x); }
template <class T, class U>
void rd1(pair<T, U> &p) {
return rd1(p.first), rd1(p.second);
}
template <size_t N = 0, typename T>
void rd1_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd1(x);
rd1_tuple<N + 1>(t);
}
}
template <class... T>
void rd1(tuple<T...> &tpl) {
rd1_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd1(array<T, N> &x) {
for (auto &d: x) rd1(d);
}
template <class T>
void rd1(vc<T> &x) {
for (auto &d: x) rd1(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd1(h), read(t...);
}
void wt1(const char c) {
if (por == SIZ) flush();
obuf[por++] = c;
}
template <typename T>
void wt1_integer(T x) {
if (por > SIZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <class T, enable_if_t<is_integral_v<T>, int> = 0>
void wt1(T x) { wt1_integer(x); }
template <class T, class U>
void wt1(const pair<T, U> &val) {
wt1(val.first);
wt1(' ');
wt1(val.second);
}
template <size_t N = 0, typename T>
void wt1_tuple(const T &t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt1(' '); }
const auto x = std::get<N>(t);
wt1(x);
wt1_tuple<N + 1>(t);
}
}
template <class... T>
void wt1(const tuple<T...> &tpl) {
wt1_tuple(tpl);
}
template <class T, size_t S>
void wt1(const array<T, S> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt1(' ');
wt1(val[i]);
}
}
template <class T>
void wt1(const vector<T> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt1(' ');
wt1(val[i]);
}
}
template <class Head, class... Tail>
void write(Head &&head, Tail &&... tail) {
wt1(head);
write(std::forward<Tail>(tail)...);
}
void print() { wt1('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt1(head);
if (sizeof...(Tail)) wt1(' ');
print(std::forward<Tail>(tail)...);
}
} // namespace fastio
struct Dummy {
Dummy() { atexit(fastio::flush); }
} dummy;
namespace internal
{
template <class... Ts>
void READnodump(Ts &...a) { fastio::read(a...); }
template <class T>
void READVECnodump(int n, vc<T> &v)
{
v.resize(n);
READnodump(v);
}
template <class T, class... Ts>
void READVECnodump(int n, vc<T> &v, vc<Ts> &...vs)
{ READVECnodump(n, v), READVECnodump(n, vs...); }
template <class T>
void READVEC2nodump(int n, int m, vvc<T> &v)
{
v.assign(n, vc<T>(m));
READnodump(v);
}
template <class T, class... Ts>
void READVEC2nodump(int n, int m, vvc<T> &v, vvc<Ts> &...vs)
{ READVEC2nodump(n, m, v), READVEC2nodump(n, m, vs...); }
template <class T>
void READJAGnodump(int n, vvc<T> &v)
{
v.resize(n);
repi(i, n)
{
int k;
READnodump(k);
READVECnodump(k, v[i]);
}
}
template <class T, class... Ts>
void READJAGnodump(int n, vvc<T> &v, vvc<Ts> &...vs)
{ READJAGnodump(n, v), READJAGnodump(n, vs...); }
}; // namespace internal
#define READ(...) internal::READnodump(__VA_ARGS__); dump(__VA_ARGS__)
#define IN(T, ...) T __VA_ARGS__; READ(__VA_ARGS__)
#define LL(...) IN(ll, __VA_ARGS__)
#define PRINT fastio::print
template <class T, class U, class P>
pair<T, U> operator+=(pair<T, U> &a, const P &b)
{
a.first += b.first;
a.second += b.second;
return a;
}
template <class T, class U, class P>
pair<T, U> operator+(pair<T, U> &a, const P &b) { return a += b; }
template <class T, size_t n, class A>
array<T, n> operator+=(array<T, n> &a, const A &b)
{
for (size_t i = 0; i < n; i++)
a[i] += b[i];
return a;
}
template <class T, size_t n, class A>
array<T, n> operator+(array<T, n> &a, const A &b) { return a += b; }
namespace internal
{
template <size_t... I, class A, class B>
auto tuple_add_impl(A &a, const B &b, const index_sequence<I...>)
{
((get<I>(a) += get<I>(b)), ...);
return a;
}
}; // namespace internal
template <class... Ts, class Tp>
tuple<Ts...> operator+=(tuple<Ts...> &a, const Tp &b)
{ return internal::tuple_add_impl(a, b, make_index_sequence<tuple_size_v<tuple<Ts...>>>{}); }
template <class... Ts, class Tp>
tuple<Ts...> operator+(tuple<Ts...> &a, const Tp &b) { return a += b; }
namespace internal
{
};
mt19937_64 mt;
template <class T>
struct larger_int;
#define LARGER_INT(T, U) \
template <> \
struct larger_int<T> \
{ \
using type = U; \
};
LARGER_INT(signed char, short)
LARGER_INT(short, int)
LARGER_INT(int, long long)
LARGER_INT(long, __int128_t)
LARGER_INT(long long, __int128_t)
LARGER_INT(unsigned char, unsigned short)
LARGER_INT(unsigned short, unsigned int)
LARGER_INT(unsigned int, unsigned long long)
LARGER_INT(unsigned long, __uint128_t)
LARGER_INT(unsigned long long, __uint128_t)
#undef LARGER_INT
template <class T>
using larger_int_t = typename larger_int<T>::type;
namespace internal
{
template <class T>
constexpr ll powmod_constexpr(ll x, ll n, T m)
{
if (m == 1)
return 0;
using U = make_unsigned_t<T>;
using L = larger_int_t<U>;
U r = 1, y = safemod(x, m);
while (n)
{
if (n & 1)
r = L(r) * y % m;
y = L(y) * y % m;
n >>= 1;
}
return r;
}
template <class T>
constexpr bool isprime_constexpr(T n)
{
if constexpr (sizeof(T) > 4)
{
if (n <= INT_MAX)
return isprime_constexpr<int>(n);
}
if (n <= 1)
return false;
if (n == 2 || n == 7 || n == 61)
return true;
if (n % 2 == 0)
return false;
ll d = n - 1;
while (d % 2 == 0)
d /= 2;
using U = make_unsigned_t<T>;
using L = larger_int_t<U>;
auto miller_rabin = [&](const auto &bases) constexpr
{
for (ll a : bases)
{
ll t = d, y = powmod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1)
{
y = L(y) * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0)
return false;
}
return true;
};
if constexpr(sizeof(T) <= 4)
{
constexpr ll bases[3] = {2, 7, 61};
return miller_rabin(bases);
}
else
{
constexpr ll bases[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
return miller_rabin(bases);
}
}
template <auto n>
constexpr bool isprime = isprime_constexpr(n);
};
namespace internal
{
template <auto M>
struct policy_static
{
using mod_type = decltype(M);
using value_type = make_unsigned_t<mod_type>;
using calc_type = larger_int_t<value_type>;
static constexpr bool is_prime = isprime_constexpr(M);
static constexpr mod_type mod() { return M; }
static constexpr value_type umod() { return M; }
static constexpr value_type init(value_type v) { return v; }
static constexpr mod_type val(value_type v) { return v; }
static constexpr value_type mul(value_type a, value_type b)
{
return (value_type)((calc_type(a) * b) % M);
}
};
};
namespace internal
{
struct barrett32
{
uint m;
ull im;
explicit barrett32(uint m) : m(m), im((ull)(-1) / m + 1) {}
uint umod() const { return m; }
uint mul(uint a, uint b) const
{
ull z = a;
z *= b;
ull x = ull((u128(z) * im) >> 64);
ull y = x * m;
return uint(z - y + (z < y ? m : 0));
}
};
template <int id>
struct policy_barrett32
{
using value_type = uint;
using calc_type = ull;
using mod_type = int;
static constexpr bool is_prime = false;
static inline barrett32 reducer{998244353};
static void set_mod(mod_type m) { reducer = barrett32(m); }
static mod_type mod() { return reducer.umod(); }
static value_type umod() { return reducer.umod(); }
static value_type init(value_type v) { return v; }
static mod_type val(value_type v) { return v; }
static value_type mul(value_type a, value_type b) { return reducer.mul(a, b); }
};
};
namespace internal
{
inline constexpr ull inv64(ull a)
{
ull x = a;
while (a * x != 1) x *= 2 - a * x;
return x;
}
struct montgomery64odd
{
ull m, im, sq;
explicit montgomery64odd(ull m) : m(m), im(inv64(m)), sq(-u128(m) % m) {}
ull umod() const { return m; }
ull reduce(u128 x) const
{
auto t = (x + u128(m) * (-im * ull(x))) >> 64;
if (t >= m) t -= m;
return (ull)t;
}
ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * sq); }
};
struct montgomery64
{
ull m, mx, imx, d, q;
uint b;
explicit montgomery64(ull m) : m(m)
{
b = countr_zero(m), mx = m >> b;
imx = inv64(mx);
d = powmod_constexpr((mx + 1) / 2, b, mx);
u128 sq = -u128(mx) % mx;
q = (1 + (((sq - 1) * d) << b)) % m;
}
ull umod() const { return m; }
ull reduce(u128 x) const
{
ull p = x & MASK(b);
x = (x >> b) + p * d;
ull y = p << (64 - b);
auto t = (x + u128(mx) * (imx * (y - ull(x)))) >> (64 - b);
if (t >= m) { t -= m; if (t >= m) t -= m; }
return (ull)t;
}
ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * q); }
};
template <int id>
struct policy_montgomery64_odd
{
using value_type = ull;
using calc_type = u128;
using mod_type = ll;
static constexpr bool is_prime = false;
static inline montgomery64odd reducer{(1LL << 61) - 1};
static void set_mod(mod_type m) { reducer = montgomery64odd(m); }
static mod_type mod() { return reducer.umod(); }
static value_type umod() { return reducer.umod(); }
static value_type init(value_type v) { return reducer.inv_reduce(v); }
static mod_type val(value_type v) { return reducer.reduce(v); }
static value_type mul(value_type a, value_type b) { return reducer.reduce((calc_type)a * b); }
};
template <int id>
struct policy_montgomery64
{
using value_type = ull;
using calc_type = u128;
using mod_type = ll;
static constexpr bool is_prime = false;
static inline montgomery64 reducer{(1LL << 61) - 1};
static void set_mod(mod_type m) { reducer = montgomery64(m); }
static mod_type mod() { return reducer.umod(); }
static value_type umod() { return reducer.umod(); }
static value_type init(value_type v) { return reducer.inv_reduce(v); }
static mod_type val(value_type v) { return reducer.reduce(v); }
static value_type mul(value_type a, value_type b) { return reducer.reduce((calc_type)a * b); }
};
};
template <class T = ll>
constexpr tuple<T, T, T> extgcd(T a, T b)
{
if (a == 0 && b == 0)
return {0, 0, 0};
T x1 = 1, y1 = 0, z1 = a;
T x2 = 0, y2 = 1, z2 = b;
while (z2 != 0)
{
T q = z1 / z2;
tie(x1, x2) = make_pair(x2, x1 - q * x2);
tie(y1, y2) = make_pair(y2, y1 - q * y2);
tie(z1, z2) = make_pair(z2, z1 - q * z2);
}
if (z1 < 0)
x1 = -x1, y1 = -y1, z1 = -z1;
return {z1, x1, y1};
}
namespace internal
{
template <class Policy>
struct modint_impl
{
using V = typename Policy::value_type;
using M = typename Policy::mod_type;
using mint = modint_impl;
private:
V _v;
public:
static constexpr M mod() { return Policy::mod(); }
template <class T = Policy>
static auto set_mod(M m) -> decltype(T::set_mod(m)) { return T::set_mod(m); }
modint_impl() : _v(0) {}
template <class T, typename = enable_if_t<is_integral_ext<T>>>
modint_impl(T v)
{
V rem;
if constexpr (is_signed_ext<T>)
{
using S = make_signed_t<V>;
S x = v % S(Policy::umod());
if (x < 0)
x += Policy::umod();
rem = x;
}
else
rem = V(v % Policy::umod());
_v = Policy::init(rem);
};
M val() const { return Policy::val(_v); }
mint &operator+=(const mint &rhs)
{
_v += rhs._v;
if (_v >= Policy::umod())
_v -= Policy::umod();
return *this;
}
mint &operator-=(const mint &rhs)
{
_v -= rhs._v;
if (_v >= Policy::umod())
_v += Policy::umod();
return *this;
}
mint &operator*=(const mint &rhs)
{
_v = Policy::mul(_v, rhs._v);
return *this;
}
mint &operator/=(const mint &rhs)
{
return *this *= rhs.inv();
}
mint &operator++()
{
_v++;
if (_v == Policy::umod())
_v = 0;
return *this;
}
mint &operator--()
{
if (_v == 0)
_v = Policy::umod();
_v--;
return *this;
}
mint operator++(int)
{
mint res = *this;
++(*this);
return res;
}
mint operator--(int)
{
mint res = *this;
--(*this);
return res;
}
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
template <class T>
mint pow(T n) const
{
assert(n >= 0);
mint x = *this, r = 1;
while (n)
{
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const
{
if constexpr (Policy::is_prime)
{
return pow(mod() - 2);
}
else
{
auto [g, x, y] = extgcd<M>(val(), mod());
assert(g == 1);
return mint(x);
}
}
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; }
friend void rd1(mint &x)
{
long long a;
fastio::rd1(a);
x = a;
}
friend void wt1(const mint &x)
{
fastio::wt1(x.val());
}
};
};
template <int mod>
using static_modint32 = internal::modint_impl<internal::policy_static<mod>>;
template <int id>
using dynamic_modint32 = internal::modint_impl<internal::policy_barrett32<id>>;
template <ll mod>
using static_modint64 = internal::modint_impl<internal::policy_static<mod>>;
template <int id>
using dynamic_modint64_odd = internal::modint_impl<internal::policy_montgomery64_odd<id>>;
template <int id>
using dynamic_modint64 = internal::modint_impl<internal::policy_montgomery64<id>>;
using modint998244353 = static_modint32<998244353>;
template <class T>
struct is_modint : std::false_type
{
};
template <class Policy>
struct is_modint<internal::modint_impl<Policy>> : std::true_type
{
};
template <class T>
inline constexpr bool is_modint_v = is_modint<T>::value;
template <class T>
struct is_static_modint : false_type {};
template <int m>
struct is_static_modint<static_modint32<m>> : true_type {};
template <ll m>
struct is_static_modint<static_modint64<m>> : true_type {};
template <class T>
inline constexpr bool is_static_modint_v = is_static_modint<T>::value;
template <class T>
struct is_dynamic_modint : false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint32<id>> : true_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint64_odd<id>> : true_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint64<id>> : true_type {};
template <class T>
inline constexpr bool is_dynamic_modint_v = is_dynamic_modint<T>::value;
template <typename, typename = void>
struct has_mod : std::false_type
{
};
template <typename T>
struct has_mod<T, std::void_t<decltype(T::mod())>> : std::true_type
{
};
template <class mint>
struct PowerTable
{
private:
decltype(mint::mod()) mod;
mint base;
vc<mint> pw;
public:
PowerTable() {}
PowerTable(const mint &base) : mod(mint::mod()), base(base), pw(1, 1) {}
void reserve(int n)
{
if (mod != mint::mod())
{
mod = mint::mod();
pw = {1};
}
int i = pw.size();
if (n < i)
return;
pw.resize(n + 1);
for (; i <= n; i++)
pw[i] = pw[i - 1] * base;
}
mint pow(int n)
{
reserve(n);
return pw[n];
}
};
#if __cplusplus >= 202302L
namespace cpp_dump
{
struct mint_to_rat_fn
{
template <class T>
constexpr auto operator()(const T &x) const -> decltype(mint_to_rat(x))
{
return mint_to_rat(x);
}
};
struct rat_closure : std::ranges::range_adaptor_closure<rat_closure>
{
template <typename T>
constexpr auto operator()(T &&t) const
{
if constexpr (!std::ranges::range<T> && std::invocable<mint_to_rat_fn, decltype(std::forward<T>(t))>)
{
return mint_to_rat_fn{}(std::forward<T>(t));
}
else if constexpr (std::ranges::range<T>)
{
using Ref = std::ranges::range_reference_t<T>;
if constexpr (std::invocable<mint_to_rat_fn, decltype(std::forward<Ref>(std::declval<Ref>()))>)
{
return std::forward<T>(t) | std::views::transform(mint_to_rat_fn{});
}
else if constexpr (std::ranges::range<Ref>)
{
return std::forward<T>(t) | std::views::transform([this](auto &&inner)
{ return (*this)(std::forward<decltype(inner)>(inner)); });
}
else
{
static_assert(false);
}
}
else
{
static_assert(false);
}
}
};
template <typename T>
requires(!std::ranges::range<T> && std::invocable<mint_to_rat_fn, T>)
constexpr auto operator|(T &&t, const rat_closure &c)
{
return c(std::forward<T>(t));
}
}
#endif
using mint = modint998244353;
void init()
{
oj(mt.seed(random_device()()));
}
template <class UFData, bool compress = true>
struct UnionFind
{
friend UFData;
protected:
vc<int> par;
vc<typename UFData::VData> vdat;
public:
typename UFData::GData gdat;
UnionFind() {}
UnionFind(int n) : par(n, -1), vdat(n), gdat(n)
{ repi(i, n) vdat[i] = typename UFData::VData(i); }
virtual int leader(int x)
{
assert(0 <= x && x < SZ<int>(par));
if (par[x] < 0)
return x;
if constexpr (compress)
return par[x] = leader(par[x]);
else
return leader(par[x]);
}
template <class I = ll>
I size(int x) { return -par[leader(x)]; }
bool same(int x, int y) { return leader(x) == leader(y); }
template <class I = ll>
I merge(int x, int y, const typename UFData::EWeight &w = 1)
{
x = leader(x), y = leader(y);
if (x == y)
{
UFData::add_edge_same(*this, x, w);
return x;
}
if (-par[x] < -par[y])
swap(x, y);
par[x] += par[y], par[y] = x;
UFData::add_edge_diff(*this, x, y, w);
return x;
}
};
template <class EWeight_ = ll>
struct UFDataEmpty
{
struct VData
{
VData() {}
VData(int) {}
};
struct GData
{
GData() {}
GData(int) {}
};
using EWeight = EWeight_;
template <class UF>
static void add_edge_diff(UF &, int, int, EWeight) {}
template <class UF>
static void add_edge_same(UF &, int, EWeight) {}
};
ll naive(ll N, ll M)
{
UnionFind<UFDataEmpty<>> uf(N + 1);
ll ans = 0;
vtlll E;
rep(x, 1, N + 1) rep(y, x + 1, N + 1)
{
E.eb((x + y) % M, x, y);
}
sort(ALL(E));
fec([w, u, v] : E)
{
if (uf.same(u, v))
continue;
uf.merge(u, v);
ans += w;
}
return ans;
}
ll solve(ll N, ll M)
{
if (N >= M)
return M / 2;
else
{
ll tmp1 = N - M + M / 2;
ll tmp2 = M - N <= 2 ? 0 : (M - N) * (M - N + 1) / 2 - 1 - 2;
ll tmp3 = M - N == 1 ? 0 : M - N + 1;
ll ans = tmp1 + tmp2 + tmp3;
dump(tmp1, tmp2, tmp3);
return ans;
}
}
void main2()
{
LL(N, M);
PRINT(solve(N, M));
}
void test()
{
rep(N, 2, 10) rep(M, 1, 2 * N + 1)
{
ll god = naive(N, M);
ll ans = solve(N, M);
dump(N, M, god, ans);
if (god != ans)
return;
}
}
template <auto init, auto main2, auto test>
struct Main
{
Main()
{
cauto CERR = [](string val, string color)
{
string s = "\033[" + color + "m" + val + "\033[m";
/* コードテストで確認する際にコメントアウトを外す
cerr << val;
//*/
};
CERR("\n[FAST_IO]\n\n", "32");
cout << fixed << setprecision(20);
init();
CERR("\n[MULTI_TESTCASE]\n\n", "33");
local(while (true))
{
dump("T");
IN(uint, T);
while (T--)
{
dump("new testcase");
main2();
}
}
}
};
Main<init, main2, test> main_dummy;
}
int main() {}