結果
| 問題 | No.2544 Many RMQ Problems |
| ユーザー |
 zjsdut
|
| 提出日時 | 2023-12-19 22:21:12 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 150 ms / 2,000 ms |
| コード長 | 34,075 bytes |
| コンパイル時間 | 1,588 ms |
| コンパイル使用メモリ | 129,096 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-27 09:01:06 |
| 合計ジャッジ時間 | 4,392 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 149 ms
6,940 KB |
| testcase_04 | AC | 131 ms
6,940 KB |
| testcase_05 | AC | 118 ms
6,940 KB |
| testcase_06 | AC | 137 ms
6,944 KB |
| testcase_07 | AC | 63 ms
6,940 KB |
| testcase_08 | AC | 25 ms
6,944 KB |
| testcase_09 | AC | 2 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 2 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 2 ms
6,944 KB |
| testcase_14 | AC | 2 ms
6,944 KB |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 2 ms
6,944 KB |
| testcase_17 | AC | 2 ms
6,940 KB |
| testcase_18 | AC | 2 ms
6,940 KB |
| testcase_19 | AC | 149 ms
6,944 KB |
| testcase_20 | AC | 149 ms
6,944 KB |
| testcase_21 | AC | 149 ms
6,940 KB |
| testcase_22 | AC | 149 ms
6,940 KB |
| testcase_23 | AC | 150 ms
6,940 KB |
| testcase_24 | AC | 2 ms
6,940 KB |
| testcase_25 | AC | 2 ms
6,940 KB |
| testcase_26 | AC | 149 ms
6,944 KB |
| testcase_27 | AC | 2 ms
6,944 KB |
| testcase_28 | AC | 150 ms
6,940 KB |
ソースコード
/**
* code generated by JHelperX
* More info: https://github.com/GoBigorGoHome/JHelperX
* @author zjs
*/
#if not defined LOCAL and not defined NDEBUG
#define NDEBUG
#endif
#define debug(...)
#define show(...)
extern const bool show_all_failed_tests = false;
extern const bool compare_real_numbers = false;
// #define INTERACTIVE_MODE //对于交互题，取消此行注释。
//
// Created by zjsdu on 5/28/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#include <string>
#include <cassert>
#include <queue>
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#include <iostream>
#include <vector>
#include <tuple>
//
// Created by zjsdu on 10/22/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#define JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#include <type_traits>
#if __cplusplus >= 201703L
template<typename T> T type();// no definition
template<typename Container> auto value_type_of_() {
if constexpr (std::is_array_v<Container>)
return type<std::remove_extent_t<Container>>();
else
return type<typename Container::value_type>();
}
template<typename Container>
using value_type_of =
decltype(value_type_of_<std::remove_reference_t<Container>>());
#else
template <typename Container>
struct value_type_of_impl // default, non-array
{
using type = typename Container::value_type;
};
template <typename T, std::size_t N>
struct value_type_of_impl<T[N]> // arrays
{
using type = T;
};
template <typename Container>
using value_type_of = typename value_type_of_impl<Container>::type;
#endif
// Source: https://foonathan.net/2020/10/iife-metaprogramming/
#if __cplusplus >= 201703L
namespace is_iterable_impl {
using std::begin;
using std::end;
template<typename T>
using check_specs = std::void_t<
std::enable_if_t<
std::is_same<decltype(begin(std::declval<T &>())),// has begin()
decltype(end(std::declval<T &>())) // has end()
>::value>,// ... begin() and end() are the same type ...
decltype(*begin(std::declval<T &>()))>;// ... which can be dereferenced
template<typename, typename = void> struct is_iterable : std::false_type {};
// specialization
template<class T> struct is_iterable<T, check_specs<T>> : std::true_type {};
}// namespace is_iterable_impl
template<class T> using is_iterable = is_iterable_impl::is_iterable<T>;
template<typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
// Source: https://stackoverflow.com/a/53429396/6793559
template<typename T>
using is_string =
std::disjunction<std::is_same<char *, typename std::decay_t<T>>,
std::is_same<const char *, typename std::decay_t<T>>,
std::is_same<std::string, typename std::decay_t<T>>>;
template<typename T> constexpr bool is_string_v = is_string<T>::value;
// Source: https://stackoverflow.com/a/57812868/6793559
template<template<typename...> typename Target, typename Aux, typename... Ts>
struct is_specialized_for_impl : std::false_type {};
template<template<typename...> typename Target, typename... Args>
struct is_specialized_for_impl<Target, decltype(sizeof(Target<Args...>)),
Args...> : std::true_type {};
template<template<typename...> typename Target, typename... Args>
using is_specialized_for =
is_specialized_for_impl<Target, std::size_t, Args...>;
template<template<typename...> typename Target, typename... Args>
constexpr bool is_specialized_for_v =
is_specialized_for<Target, Args...>::value;
template<typename T>
using is_tuple_like = is_specialized_for<std::tuple_size, T>;
template<typename T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
template<typename T, typename = void> struct remove_all_extents_ {
typedef std::remove_reference_t<T> type;
};
template<typename T>
struct remove_all_extents_<T, std::void_t<decltype(std::declval<T>()[0])>> {
typedef
typename remove_all_extents_<decltype(std::declval<T>()[0])>::type type;
};
template<typename T, typename = void>
struct rank_ : public std::integral_constant<std::size_t, 0> {};
template<typename T>
struct rank_<T, std::void_t<decltype(std::declval<T>()[0])>>
: public std::integral_constant<
std::size_t, rank_<decltype(std::declval<T>()[0])>::value + 1> {};
#endif
#endif// JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
struct fast_ios {
fast_ios() {
#ifndef INTERACTIVE_MODE
std::cin.tie(nullptr);
#endif
std::ios::sync_with_stdio(false);
std::cout.precision(15);
std::cout << std::fixed;
};
} const fast_ios_;
namespace io {
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p);
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t);
template<typename... Ts>
std::ostream &operator<<(std::ostream &, const std::tuple<Ts...> &);
template<typename T, typename U>
std::istream &operator>>(std::istream &in, std::pair<T, U> &p) {
in >> p.first >> p.second;
return in;
}
template<typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &vec) {
for (auto &x : vec)
stream >> x;
return stream;
}
#if __cplusplus >= 201703L
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t) {
std::apply([&in](auto &...args) { ((in >> args), ...); }, t);
return in;
}
template<class... Args> void scan(Args &...args) {
((std::cin >> args), ...);
}
template<typename Container,
typename = std::enable_if_t<std::conjunction_v<
is_iterable<Container>, std::negation<is_string<Container>>>>>
std::ostream &operator<<(std::ostream &out, const Container &container) {
using std::begin;
using value_type =
std::remove_reference_t<decltype(*begin(std::declval<Container &>()))>;
constexpr char delimiter =
is_iterable_v<value_type> or is_tuple_like_v<value_type> ? '\n' : ' ';
bool first = true;
for (auto &element : container) {
if (first)
first = false;
else
out << delimiter;
out << element;
}
return out;
}
// Source: https://en.cppreference.com/w/cpp/utility/apply
template<typename... Ts>
std::ostream &operator<<(std::ostream &out, const std::tuple<Ts...> &theTuple) {
std::apply(
[&out](Ts const &...tupleArgs) {
std::size_t n{0};
((out << tupleArgs << (++n != sizeof...(Ts) ? " " : "")), ...);
},
theTuple);
return out;
}
#endif
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p) {
out << p.first << ' ' << p.second;
return out;
}
template<typename T>
std::ostream &operator<<(std::ostream &out,
const std::vector<std::vector<T>> &t) {
bool is_first = true;
for (const auto &row : t) {
if (is_first)
is_first = false;
else
out << '\n';
out << row;
}
return out;
}
std::ostream &operator<<(std::ostream &os, __int128 n) {
if (n < 0) {
n = -n;
os << '-';
}
std::string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
for (int i = (int) s.size() - 1; i >= 0; i--)
os << s[i];
return os;
}
#if __cplusplus >= 201703L
template<typename... Args> void pt(Args &&...args) {
((std::cout << args << ' '), ...);
}
template<typename First, typename... Args>
void pl(const First &first, const Args &...args) {
std::cout << first;
((std::cout << ' ' << args), ...);
std::cout << '\n';
}
template<typename... Args> void pn(const Args &...args) {
((std::cout << args << '\n'), ...);
}
#endif
}// namespace io
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
//
// Created by zjsdu on 10/26/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
template<typename T, unsigned Dimension> struct ndvec {
using type = std::vector<typename ndvec<T, Dimension - 1>::type>;
};
template<typename T> struct ndvec<T, 0> { using type = T; };
// arbitrary-dimensional array that allows non-constexpr extents.
// Usage: ndarray<dimension, value_type> arr(extents..., init_value);
// An initial value for all array items can be specified if all extensions are
// specified.
// Examples:
// ndarray<2, int> a(2, 3, -1);
// ndarray<3, int> b(2, 3, 4);
// ndarray<3, int> c(2, 3);
template<unsigned dimension, typename T>
class ndarray : public ndvec<T, dimension>::type {
using base_type = typename ndvec<T, dimension>::type;
using value_type = typename base_type::value_type;
using base_type::base_type;
public:
template<typename... Args>
ndarray(unsigned d, Args... args)
: std::vector<value_type>(d, ndarray<dimension - 1, T>(args...)) {}
};
template<typename T> class ndarray<1, T> : public std::vector<T> {
using std::vector<T>::vector;
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
//
// Created by zjsdu on 2/9/2021.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define CALL_WITH_EXPANDED_ARGS(function, ...) function(__VA_ARGS__)
#define JOIN_IMPL(arg1, arg2) arg1##arg2
#define JOIN(arg1, arg2) JOIN_IMPL(arg1, arg2)
#define EXPAND_1(...) __VA_ARGS__
#define EXPAND_4(...) EXPAND_1(EXPAND_1(EXPAND_1(__VA_ARGS__)))
#define EXPAND_13(...) EXPAND_4(EXPAND_4(EXPAND_4(__VA_ARGS__)))
#define PAUSE
#define COMMA() ,
#define TERMINATE(...)
#define SELECT_SECOND_ARG(arg1, arg2, ...) arg2
#define CONDITIONAL(peek, arg1, arg2) \
CALL_WITH_EXPANDED_ARGS(SELECT_SECOND_ARG, COMMA peek arg1, arg2)
#define TERMINATE_OR(peek, arg) CONDITIONAL(peek, TERMINATE, arg)
#define FOR_EACH_2_IMPL0(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL1) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2_IMPL1(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL0) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2(function, ...) \
EXPAND_13(FOR_EACH_2_IMPL0(function, __VA_ARGS__, ()))
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using vi = std::vector<int>;
using vs = std::vector<std::string>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;
using pil = std::pair<int, ll>;
using pll = std::pair<ll, ll>;
using vii = std::vector<pii>;
template<typename T>
using pq = std::priority_queue<T>;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename... Ts> using vt = std::vector<std::tuple<Ts...>>;
template<typename T> using vv = ndarray<2, T>;
template<typename T> struct range_tuple {
const T &ref = beg;
T beg;
const T end;
range_tuple(T b, T e) : beg(b), end(e) {}
};
#define rng4(i, a, b, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type<decltype(a), decltype(b)>::type>(a, \
b); \
i < JOIN(end_, __LINE__); JOIN(iter_, __LINE__) += c)
#define rng3(i, a, b) rng4(i, a, b, 1)
#define rng2(i, n) rng3(i, 0, n)
#define GET4(_1, _2, _3, _4, NAME, ...) NAME
#define rng(...) GET4(__VA_ARGS__, rng4, rng3, rng2)(__VA_ARGS__)
#define up4(i, a, b, c) rng (i, a, b + 1, c)
#define up3(i, a, b) up4(i, a, b, 1)
#define up(...) GET4(__VA_ARGS__, up4, up3, NO_IMPL)(__VA_ARGS__)
#define down4(i, b, a, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type<decltype(a), decltype(b)>::type>(b, \
a); \
i >= JOIN(end_, __LINE__); JOIN(iter_, __LINE__) -= c)
#define down3(i, b, a) down4(i, b, a, 1)
#define down(...) GET4(__VA_ARGS__, down4, down3, NO_IMPL)(__VA_ARGS__)
#define rep(n) \
for (auto JOIN(_iter_, __LINE__) = n; JOIN(_iter_, __LINE__) > 0; \
--JOIN(_iter_, __LINE__))
#define FOR_LAST_OPERATION_IMPL(arg1, arg2) arg1] : arg2
#define FOR_NORMAL_OPERATION_IMPL(arg1, arg2) arg1,
#define FOR_IMPL0(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL1) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL1(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL0) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL3(arg1, arg2, peek, ...) \
CONDITIONAL(peek, for (auto && arg1 : arg2), \
for (auto && [EXPAND_13(FOR_IMPL0(arg1, arg2, peek, __VA_ARGS__))))
#define FOR(...) FOR_IMPL3(__VA_ARGS__, ())
#define ALL(x) std::begin(x), std::end(x)
// hat off to 300iq
#define RALL(x) std::rbegin(x), std::rend(x)
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define ep emplace
#define SZ(x) (int) (x).size()
#define rp(...) return pl(__VA_ARGS__)
#define rpn(...) return pn(__VA_ARGS__)
#define adv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i < JOIN(_n_, __LINE__); ++i)
#define radv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i > JOIN(_n_, __LINE__); --i)
#define INT(...) \
int __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define NL \
[] { \
std::cout << '\n'; \
}()
#define RI \
([] { \
int x; \
std::cin >> x; \
return x; \
})()
#define READ_VI(NAME, LEN) \
std::vector<int> NAME(LEN); \
io::scan(NAME);
#define VI(...) FOR_EACH_2(READ_VI, __VA_ARGS__)
#define READ_VII(NAME, LEN) \
std::vector<std::pair<int, int>> NAME(LEN); \
io::scan(NAME);
#define VII(...) FOR_EACH_2(READ_VII, __VA_ARGS__)
#define READ_VL(NAME, LEN) \
std::vector<long long> NAME(LEN); \
io::scan(NAME);
#define VL(...) FOR_EACH_2(READ_VL, __VA_ARGS__)
#define READ_VS(NAME, LEN) \
std::vector<std::string> NAME(LEN); \
io::scan(NAME);
#define VS(...) FOR_EACH_2(READ_VS, __VA_ARGS__)
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#ifndef CP_UTILS
#define CP_UTILS
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <numeric>
#include <set>
#include <random>
#include <chrono>
inline void Yn(bool p) {
std::cout << (p ? "Yes\n" : "No\n");
}
inline void YN(bool p) {
std::cout << (p ? "YES\n" : "NO\n");
}
inline void yn(bool p) {
std::cout << (p ? "yes\n" : "no\n");
}
template<typename Container> Container inc(Container &&c) {
for (auto &e : c)
++e;
return std::forward<Container>(c);
}
template<typename Container> Container dec(Container &&c) {
for (auto &e : c)
--e;
return std::forward<Container>(c);
}
template<typename A, typename B>
bool chkmin(A& a, const B& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename A, typename B>
bool chkmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __cplusplus >= 201703L
template<typename A, typename B, typename... C>
bool chkmin(A& a, const B& b, const C&... c) {
if (B res = std::min<B>({b, c...}); res < a) {
a = res;
return true;
}
return false;
}
template<typename A, typename B, typename... C>
bool chkmax(A& a, const B& b, const C&... c) {
if (B res = std::max<B>({b, c...}); res > a) {
a = res;
return true;
}
return false;
}
#endif
template<typename T, typename U>
void append(T &container1, const U &container2) {
container1.insert(container1.end(), container2.begin(), container2.end());
}
template<typename T> int argmin(const std::vector<T> &a) {
return (int) (std::min_element(a.begin(), a.end()) - a.begin());
}
template<typename T> int argmax(const std::vector<T> &a) {
return (int) (std::max_element(a.begin(), a.end()) - a.begin());
}
template<typename Container> Container reverse(Container &&c) {
std::reverse(std::begin(c), std::end(c));
return std::forward<Container>(c);
}
template<typename Sequence> Sequence rev_copy(Sequence a) {
std::reverse(std::begin(a), std::end(a));
return a;
}
template<typename Sequence> Sequence uniq(Sequence &&s) {
std::sort(std::begin(s), std::end(s));
s.erase(std::unique(std::begin(s), std::end(s)), std::end(s));
return std::forward<Sequence>(s);
}
template<typename Container> auto max(const Container &c) {
assert(c.size() > 0);
return *std::max_element(std::begin(c), std::end(c));
}
template<typename Container> auto min(const Container &c) {
assert(c.size() > 0);
return *std::min_element(std::begin(c), std::end(c));
}
template<typename Array> int maxi(const Array &a) {
assert(a.size() > 0);
return int(std::max_element(std::begin(a), std::end(a)) - std::begin(a));
}
template<typename Array> int mini(const Array &a) {
assert(a.size() > 0);
return int(std::min_element(std::begin(a), std::end(a)) - std::begin(a));
}
template<typename Array, typename Value> auto lb(const Array &a, Value v) {
return std::lower_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value> auto ub(const Array &a, Value v) {
return std::upper_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value, typename Compare>
auto lb(const Array &a, Value v, Compare compare) {
return std::lower_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value, typename Compare>
auto ub(const Array &a, Value v, Compare compare) {
return std::upper_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value> int lbi(const Array &a, Value v) {
return int(lb(a, v) - std::begin(a));
}
template<typename Iter, typename Value> int lbi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::lower_bound(beg, beg + count, v) - beg);
}
template<typename Iter, typename Value> int ubi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::upper_bound(beg, beg + count, v) - beg);
}
template<typename Array, typename Value> int ubi(const Array &a, Value v) {
return int(ub(a, v) - std::begin(a));
}
template<typename Container>
Container iota(Container &&c, value_type_of<Container> v) {
std::iota(std::begin(c), std::end(c), v);
return std::forward<Container>(c);
}
template<typename T, typename Comp>
std::vector<int> argsort(const std::vector<T> &array, Comp comp) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(), [&array, comp](int i, int j) {
return comp(array[i], array[j]);
});
return res;
}
template<typename T> std::vector<int> argsort(const std::vector<T>& array) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(),
[&array](int i, int j) { return array[i] < array[j]; });
return res;
}
template<typename T> std::vector<int> order(const std::vector<T>& array) {
int n = (int) array.size();
std::vector<int> I(n);
std::iota(I.begin(), I.end(), 0);
std::sort(I.begin(), I.end(),
[&array](int i, int j) { return array[i] < array[j]; });
std::vector<int> order(n);
for (int i = 1; i < n; i++)
order[I[i]] = order[I[i - 1]] + (array[I[i - 1]] < array[I[i]]);
return order;
}
#if __cplusplus >=201703L
template<typename Container, typename Compare = void *>
Container sort(Container &&c, Compare comp = nullptr) {
if constexpr (std::is_same_v<Compare, void *>)
std::sort(std::begin(c), std::end(c));
else
std::sort(std::begin(c), std::end(c), comp);
return std::forward<Container>(c);
}
#endif
template<typename T> struct reversion_wrapper { T &iterable; };
template<typename T> auto begin(reversion_wrapper<T> w) {
using std::rbegin;
return rbegin(w.iterable);
}
template<typename T> auto end(reversion_wrapper<T> w) {
using std::rend;
return rend(w.iterable);
}
template<typename T> reversion_wrapper<T> rev_view(T &&iterable) {
return {std::forward<T>(iterable)};
}
/// @return nearest integer not less than the quotient x/y.
template<typename T, typename U> T qceil(T x, U y) {
assert(y > 0);
T q = x / y;
return q + (q * y < x);
}
/// @return nearest integer not greater than the quotient x/y.
template<typename T, typename U> T qfloor(T x, U y) {
assert(y > 0);
T q = x / y;
return q - (q * y > x);
}
template<typename T, typename U> std::pair<T, U> divmod(T x, U y) {
assert(y > 0);
T q = qfloor(x, y);
return {q, x - q * y};
};
/// @return nearest multiple of y not less than x.
template<typename T, typename U> T mceil(T x, U y) {
assert(y > 0);
return qceil(x, y) * y;
}
/// @return nearest multiple of y not greater than x.
template<typename T, typename U> T mfloor(T x, U y) {
assert(y > 0);
return qfloor(x, y) * y;
}
#if __cplusplus >= 201703L
template<class...> struct typelist {};
template<class T, class... Ts>
constexpr bool any_same = (std::is_same<T, Ts>::value || ...);
template<class F> struct y_combinator {
template<class... TLs> struct ref {
y_combinator &self;
template<class... Args> decltype(auto) operator()(Args &&...args) const {
using G = std::conditional_t<any_same<typelist<Args...>, TLs...>,
ref<TLs...>, ref<TLs..., typelist<Args...>>>;
return self.f(G{self}, std::forward<Args>(args)...);
}
};
F f;
template<class... Args> decltype(auto) operator()(Args &&...args) {
return ref<>{*this}(std::forward<Args>(args)...);
}
};
template<class F> y_combinator(F) -> y_combinator<F>;
#endif
template<typename T> constexpr T INF = std::numeric_limits<T>::max() / 2;
/// @brief Usage: acc\<type_of_sum\>(array)
template<typename T, typename U> T acc(const U& array) {
return std::accumulate(std::begin(array), std::end(array), T(0));
}
template <typename T> T acc(const std::vector<T>& array) {
return std::accumulate(array.begin(), array.end(), T(0));
}
// maps values of a into 0, 1, 2, ..., preserving order.
template<typename T> std::vector<int> normalize(const std::vector<T> &a) {
assert(not a.empty());
int n = (int) a.size();
std::vector<int> I = argsort(a);
std::vector<int> b(a.size());
b[I[0]] = 0;
for (int i = 1; i < n; i++)
b[I[i]] = b[I[i - 1]] + (a[I[i - 1]] < a[I[i]]);
return b;
}
template<typename F, typename Int>
Int binary_search(F check, Int ok, Int ng, bool check_ok = true) {
if (check_ok)
assert(check(ok));
while (std::abs(ok - ng) > 1) {
Int x = ng + (ok - ng) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template<typename T, typename Int> int bit(T a, Int i) {
return a >> i & 1;
}
#define popcnt(x) __builtin_popcountll((x))
// sign used in principle of inclusion-exclusion
int pie_sign(int s) {
assert(s >= 0);
return popcnt(s) & 1 ? -1 : 1;
}
#endif// CP_UTILS
using namespace io;
using namespace std;
//
// Created by zjsdu on 2022/1/8.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_M3_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_M3_HPP_
#ifndef ALGO_MODULAR
#define ALGO_MODULAR
//
// Created by zjsdu on 3/7/2021.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_INVERSE_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_INVERSE_HPP_
#include <utility>// std::swap
template<typename T> T inverse(T a, T m) {
assert(a != 0);
assert(m > 0);
T b = m, u = 0, v = 1;
while (a != 0) {
T t = b / a;
b -= t * a;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
assert(b == 1);
return u < 0 ? u + m : u;
}
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_INVERSE_HPP_
// tourist's modular-arithmetic class
template<typename T> class Modular {
public:
using Type = typename std::decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template<typename U> Modular(const U &x) { value = normalize(x); }
template<typename U> static Type normalize(const U &x) {
Type v;
if (-mod() <= x && x < mod())
v = static_cast<Type>(x);
else
v = static_cast<Type>(x % mod());
if (v < 0)
v += mod();
return v;
}
const Type &operator()() const { return value; }
template<typename U> explicit operator U() const {
return static_cast<U>(value);
}
constexpr static Type mod() { return T::value; }
Modular &operator+=(const Modular &other) {
if ((value += other.value) >= mod())
value -= mod();
return *this;
}
Modular &operator-=(const Modular &other) {
if ((value -= other.value) < 0)
value += mod();
return *this;
}
template<typename U> Modular &operator+=(const U &other) {
return *this += Modular(other);
}
template<typename U> Modular &operator-=(const U &other) {
return *this -= Modular(other);
}
Modular &operator++() { return *this += 1; }
Modular &operator--() { return *this -= 1; }
Modular operator++(int) {
Modular result(*this);
*this += 1;
return result;
}
Modular operator--(int) {
Modular result(*this);
*this -= 1;
return result;
}
Modular operator-() const { return Modular(-value); }
template<typename U = T>
std::enable_if_t<std::is_same<typename Modular<U>::Type, int>::value,
Modular>&
operator*=(const Modular &rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x),
d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(mod()));
value = m;
#else
value = normalize(static_cast<int64_t>(value)
* static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template<typename U = T>
std::enable_if_t<std::is_same<typename Modular<U>::Type, int64_t>::value,
Modular>&
operator*=(const Modular& rhs) {
int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value
/ mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template<typename U = T>
std::enable_if_t<not std::is_integral<typename Modular<U>::Type>::value,
Modular>&
operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular &operator/=(const Modular &other) {
return *this *= Modular(inverse(other.value, mod()));
}
template<typename U>
friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
template<typename U>
friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
template<typename U>
friend std::istream &operator>>(std::istream &stream, Modular<U> &number);
private:
Type value;
};
template<typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value == rhs.value;
}
template<typename T, typename U> bool operator==(const Modular<T> &lhs, U rhs) {
return lhs == Modular<T>(rhs);
}
template<typename T, typename U> bool operator==(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) == rhs;
}
template<typename T, typename U> bool operator!=(const Modular<T> &lhs, U rhs) {
return !(lhs == rhs);
}
template<typename T, typename U,
typename = std::enable_if_t<not std::is_same<U, Modular<T>>::value>>
bool operator!=(U lhs, const Modular<T>& rhs) {
return !(lhs == rhs);
}
template<typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value < rhs.value;
}
template<typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) += rhs;
}
template<typename T, typename U,
typename = std::enable_if_t<not std::is_same<U, Modular<T>>::value>>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
return Modular<T>(lhs) += rhs;
}
template<typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) -= rhs;
}
template<typename T, typename U,
typename = std::enable_if_t<not std::is_same<U, Modular<T>>::value>>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
return Modular<T>(lhs) -= rhs;
}
template<typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) *= rhs;
}
template<typename T, typename U,
typename = std::enable_if_t<not std::is_same<U, Modular<T>>::value>>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
return Modular<T>(lhs) *= rhs;
}
template<typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) /= rhs;
}
template<typename T, typename U,
typename = std::enable_if_t<not std::is_same<U, Modular<T>>::value>>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) /= rhs;
}
template<typename T, typename U>
Modular<T> Power(const Modular<T> &a, const U &b) {
if (b < 0)
return 0;
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1)
res *= x;
x *= x;
p >>= 1;
}
return res;
}
template<typename T> bool IsZero(const Modular<T> &number) {
return number() == 0;
}
template<typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
return stream << number();
}
template<typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &number) {
std::common_type_t<typename Modular<T>::Type, int64_t> x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
template<int md> using Mint = Modular<std::integral_constant<int, md>>;
/// 'int64_t' and 'long long' may be different types on some platforms, e.g.,
/// AtCoder. See https://atcoder.jp/contests/practice/submissions/15865276
template<int64_t md>
using Mint64 = Modular<std::integral_constant<int64_t, md>>;
using ModType = int;
struct VarMod {
static ModType value;
};
ModType VarMod::value;
ModType &md = VarMod::value;
#endif
using mint = Mint<998244353>;
mint operator""_m(unsigned long long v) {
return mint(static_cast<int>(v));
}
std::vector<mint> factorial_(1, 1);
std::vector<mint> inv_factorial_(1, 1);
mint fact(int n) {
assert(n >= 0);
while (n + 1 > (int) factorial_.size()) {
factorial_.push_back(factorial_.back() * (int) factorial_.size());
}
return factorial_[n];
}
mint inv_fact(int n) {
assert(n >= 0);
while (n + 1 > (int) inv_factorial_.size()) {
inv_factorial_.push_back(inv_factorial_.back() / (int) inv_factorial_.size());
}
return inv_factorial_[n];
}
mint C(int n, int m) {// combination
if (m < 0 or m > n)
return 0;
return fact(n) * inv_fact(m) * inv_fact(n - m);
};
mint P(int n, int m) {// permutation
if (m < 0 or m > n)
return 0;
return fact(n) * inv_fact(n - m);
}
// Number of combinations with repetition.
mint C_rep(int n, int m) {
if (n < 0 || m < 0)
return 0;
if (n == 0)
return (int) (m == 0);
return C(n + m - 1, m);
}
// Number of ways to distribute N indistinguishable balls into M bins.
mint distribute(int N, int M) {
if (N < 0 || M < 0)
return 0;
if (M == 0)
return (int) (N == 0);
return C(N + M - 1, M - 1);
}
template<typename Int> mint power(mint x, Int n) {
return Power(x, n);
}
template<int N> struct Pow {
std::vector<mint> p{1};
mint operator()(int n) {
assert(n >= 0);
while (n + 1 > (int) p.size()) {
p.push_back(N * p.back());
}
return p[n];
}
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_M3_HPP_
void solve() {
INT(n, q);
mint s = 0;
up (x, 1, n) {
s += mint(1) / (x + 1);
}
s = s * (n + 2) - n;
up (i, 1, n + 1)
s *= i;
ll t = (ll) n * (n + 1) / 2;
pl(s * power(t, q - 1) * q);
}
#include <iostream>
int main() {
#if defined FILE_IO and not defined LOCAL
freopen(FILE_IO ".in", "r", stdin);
freopen(FILE_IO ".out", "w", stdout);
#endif
solve();
return 0;
}