結果
| 問題 | No.1510 Simple Integral |
| ユーザー |
 kk2a
|
| 提出日時 | 2025-01-06 21:51:19 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 59,306 bytes |
| コンパイル時間 | 3,097 ms |
| コンパイル使用メモリ | 180,192 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2025-01-06 21:51:24 |
| 合計ジャッジ時間 | 4,516 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 43 |
ソースコード
#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
// #include <chrono>
// #include <cmath>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1
#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1
#include <functional>
#include <queue>
#include <utility>
#include <vector>
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;
template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;
#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP
// #include "type_alias.hpp"
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;
constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;
#endif // KK2_TEMPLATE_CONSTANT_HPP
// #include "constant.hpp"
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1
#include <algorithm>
#include <vector>
namespace kk2 {
template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
if constexpr (sizeof...(sizes) == 0) {
return std::vector<T>(first);
} else {
return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
}
}
template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
std::fill(std::begin(v), std::end(v), T(x));
}
template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
for (auto &u : v) fill_all(u, x);
}
template <class C> int mysize(const C &c) {
return c.size();
}
} // namespace kk2
template <class T, class S> inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S> inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
// #include "function_util.hpp"
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1
#include <array>
#include <utility>
#include <vector>
#ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP
#define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1
#include <istream>
#include <ostream>
#include <type_traits>
namespace kk2 {
#ifndef _MSC_VER
template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
or std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value
or std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_integral =
typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned =
typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template <typename 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 <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;
template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;
template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;
template <typename T> using to_unsigned = std::make_unsigned<T>;
#endif // _MSC_VER
template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;
template <typename T>
using is_function_pointer =
typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
std::true_type,
std::false_type>::type;
template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};
template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};
template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;
namespace type_traits {
struct istream_tag {};
struct ostream_tag {};
} // namespace type_traits
template <typename T>
using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value
|| std::is_same<T, std::ifstream>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value
|| std::is_same<T, std::ofstream>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;
template <typename T>
using is_istream =
typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_ostream =
typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;
} // namespace kk2
#endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP
// #include "../type_traits/type_traits.hpp"
// なんかoj verifyはプロトタイプ宣言が落ちる
namespace impl {
struct read {
template <class IStream, class T> static void all_read(IStream &is, T &x) { is >> x; }
template <class IStream, class T, class U>
static void all_read(IStream &is, std::pair<T, U> &p) {
all_read(is, p.first);
all_read(is, p.second);
}
template <class IStream, class T> static void all_read(IStream &is, std::vector<T> &v) {
for (T &x : v) all_read(is, x);
}
template <class IStream, class T, size_t F>
static void all_read(IStream &is, std::array<T, F> &a) {
for (T &x : a) all_read(is, x);
}
};
struct write {
template <class OStream, class T> static void all_write(OStream &os, const T &x) { os << x; }
template <class OStream, class T, class U>
static void all_write(OStream &os, const std::pair<T, U> &p) {
all_write(os, p.first);
all_write(os, ' ');
all_write(os, p.second);
}
template <class OStream, class T> static void all_write(OStream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); ++i) {
if (i) all_write(os, ' ');
all_write(os, v[i]);
}
}
template <class OStream, class T, size_t F>
static void all_write(OStream &os, const std::array<T, F> &a) {
for (int i = 0; i < (int)F; ++i) {
if (i) all_write(os, ' ');
all_write(os, a[i]);
}
}
};
} // namespace impl
template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
impl::read::all_read(is, p);
return is;
}
template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
impl::read::all_read(is, v);
return is;
}
template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
impl::read::all_read(is, a);
return is;
}
template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
impl::write::all_write(os, p);
return os;
}
template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
impl::write::all_write(os, v);
return os;
}
template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
impl::write::all_write(os, a);
return os;
}
#endif // KK2_TEMPLATE_IO_UTIL_HPP
// #include "io_util.hpp"
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1
#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)
#define fi first
#define se second
#define all(p) p.begin(), p.end()
#endif // KK2_TEMPLATE_MACROS_HPP
// #include "macros.hpp"
// #include "type_alias.hpp"
struct FastIOSetUp {
FastIOSetUp() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
} fast_io_set_up;
auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;
void Yes(bool b = 1) {
kout << (b ? "Yes\n" : "No\n");
}
void No(bool b = 1) {
kout << (b ? "No\n" : "Yes\n");
}
void YES(bool b = 1) {
kout << (b ? "YES\n" : "NO\n");
}
void NO(bool b = 1) {
kout << (b ? "NO\n" : "YES\n");
}
void yes(bool b = 1) {
kout << (b ? "yes\n" : "no\n");
}
void no(bool b = 1) {
kout << (b ? "no\n" : "yes\n");
}
std::istream &operator>>(std::istream &is, u128 &x) {
std::string s;
is >> s;
x = 0;
for (char c : s) {
assert('0' <= c && c <= '9');
x = x * 10 + c - '0';
}
return is;
}
std::istream &operator>>(std::istream &is, i128 &x) {
std::string s;
is >> s;
bool neg = s[0] == '-';
x = 0;
for (int i = neg; i < (int)s.size(); i++) {
assert('0' <= s[i] && s[i] <= '9');
x = x * 10 + s[i] - '0';
}
if (neg) x = -x;
return is;
}
std::ostream &operator<<(std::ostream &os, u128 x) {
if (x == 0) return os << '0';
std::string s;
while (x) {
s.push_back('0' + x % 10);
x /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
std::ostream &operator<<(std::ostream &os, i128 x) {
if (x == 0) return os << '0';
if (x < 0) {
os << '-';
x = -x;
}
std::string s;
while (x) {
s.push_back('0' + x % 10);
x /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
#endif // KK2_TEMPLATE_PROCON_HPP
// #include <kk2/template/procon.hpp>
#ifndef KK2_TEMPLATE_DEBUG_HPP
#define KK2_TEMPLATE_DEBUG_HPP 1
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#ifndef KK2_TYPE_TRAITS_MEMBER_HPP
#define KK2_TYPE_TRAITS_MEMBER_HPP 1
#include <type_traits>
namespace kk2 {
#define HAS_MEMBER_FUNC(member) \
template <typename T, typename... Ts> struct has_member_func_##member##_impl { \
template <typename U> \
static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *); \
template <typename U> static std::false_type check(...); \
using type = decltype(check<T>(nullptr)); \
}; \
template <typename T, typename... Ts> \
struct has_member_func_##member : has_member_func_##member##_impl<T, Ts...>::type {}; \
template <typename T, typename... Ts> \
using has_member_func_##member##_t = \
std::enable_if_t<has_member_func_##member<T, Ts...>::value>; \
template <typename T, typename... Ts> \
using not_has_member_func_##member##_t = \
std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;
#define HAS_MEMBER_VAR(member) \
template <typename T> struct has_member_var_##member##_impl { \
template <typename U> static std::true_type check(decltype(std::declval<U>().member) *); \
template <typename U> static std::false_type check(...); \
using type = decltype(check<T>(nullptr)); \
}; \
template <typename T> \
struct has_member_var_##member : has_member_var_##member##_impl<T>::type {}; \
template <typename T> \
using has_member_var_##member##_t = std::enable_if_t<has_member_var_##member<T>::value>; \
template <typename T> \
using not_has_member_var_##member##_t = std::enable_if_t<!has_member_var_##member<T>::value>;
HAS_MEMBER_FUNC(debug_output)
#undef HAS_MEMBER_FUNC
#undef HAS_MEMBER_VAR
} // namespace kk2
#endif // KK2_TYPE_TRAITS_MEMBER_HPP
// #include "../type_traits/member.hpp"
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
namespace debug {
#ifdef KK2
template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);
template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<T> &v);
template <class OStream, class T, size_t F, is_ostream_t<OStream> *>
void output(OStream &os, const std::array<T, F> &a);
template <class OStream, class T, class U, is_ostream_t<OStream> *>
void output(OStream &os, const std::pair<T, U> &p);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::queue<T> &q);
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::deque<T> &d);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::stack<T> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
class Key,
class T,
class Compare,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);
template <class OStream,
class Key,
class T,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t) {
if constexpr (has_member_func_debug_output<T, OStream &>::value) {
t.debug_output(os);
} else {
os << t;
}
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<T> &v) {
os << "[";
for (int i = 0; i < (int)v.size(); i++) {
output(os, v[i]);
if (i + 1 != (int)v.size()) os << ", ";
}
os << "]";
}
template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::array<T, F> &a) {
os << "[";
for (int i = 0; i < (int)F; i++) {
output(os, a[i]);
if (i + 1 != (int)F) os << ", ";
}
os << "]";
}
template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::pair<T, U> &p) {
os << "(";
output(os, p.first);
os << ", ";
output(os, p.second);
os << ")";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::queue<T> &q) {
os << "[";
std::queue<T> tmp = q;
while (!tmp.empty()) {
output(os, tmp.front());
tmp.pop();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {
os << "[";
std::priority_queue<T, Container, Compare> tmp = q;
while (!tmp.empty()) {
output(os, tmp.top());
tmp.pop();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::deque<T> &d) {
os << "[";
std::deque<T> tmp = d;
while (!tmp.empty()) {
output(os, tmp.front());
tmp.pop_front();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::stack<T> &s) {
os << "[";
std::stack<T> tmp = s;
std::vector<T> v;
while (!tmp.empty()) {
v.push_back(tmp.top());
tmp.pop();
}
for (int i = (int)v.size() - 1; i >= 0; i--) {
output(os, v[i]);
if (i != 0) os << ", ";
}
os << "]";
}
template <class OStream,
class Key,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {
os << "{";
std::set<Key, Compare, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {
os << "{";
std::multiset<Key, Compare, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {
os << "{";
std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {
os << "{";
std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class T,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {
os << "{";
std::map<Key, T, Compare, Allocator> tmp = m;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, it->first);
os << ": ";
output(os, it->second);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class T,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {
os << "{";
std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, it->first);
os << ": ";
output(os, it->second);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t, const Args &...args) {
output(os, t);
os << ' ';
output(os, args...);
}
template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {
os << '\n';
os.flush();
}
template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &os, const T &t, const Args &...args) {
output(os, t, args...);
os << '\n';
os.flush();
}
#else
template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &, const Args &...) {
}
template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &, const Args &...) {
}
#endif // KK2
} // namespace debug
} // namespace kk2
#endif // KK2_TEMPLATE_DEBUG_HPP
// #include <kk2/template/debug.hpp>
#ifndef KK2_FPS_NTT_FRIENDLY_HPP
#define KK2_FPS_NTT_FRIENDLY_HPP 1
#ifndef KK2_CONVOLUTION_CONVOLUTION_HPP
#define KK2_CONVOLUTION_CONVOLUTION_HPP 1
#include <algorithm>
#include <vector>
#ifndef KK2_MATH_MOD_BUTTERFLY_HPP
#define KK2_MATH_MOD_BUTTERFLY_HPP 1
#include <algorithm>
#ifndef KK2_MATH_MOD_PRIMITIVE_ROOT_HPP
#define KK2_MATH_MOD_PRIMITIVE_ROOT_HPP 1
#ifndef KK2_MATH_MOD_POW_MOD_HPP
#define KK2_MATH_MOD_POW_MOD_HPP 1
#include <cassert>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <class S, class T, class U> constexpr S pow_mod(T x, U n, T m) {
assert(n >= 0);
if (m == 1) return S(0);
S _m = m, r = 1;
S y = x % _m;
if (y < 0) y += _m;
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
} // namespace kk2
#endif // KK2_MATH_MOD_POW_MOD_HPP
// #include "pow_mod.hpp"
namespace kk2 {
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;
if (m == 1107296257) return 10;
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<long long>(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> static constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace kk2
#endif // KK2_MATH_MOD_PRIMITIVE_ROOT_HPP
// #include "primitive_root.hpp"
namespace kk2 {
template <class FPS, class mint = typename FPS::value_type> void butterfly(FPS &a) {
static int g = primitive_root<mint::getmod()>;
int n = int(a.size());
int h = 0;
while ((1U << h) < (unsigned int)(n)) h++;
static bool first = true;
static mint sum_e2[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
static mint sum_e3[30];
static mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
if (first) {
first = false;
int cnt2 = __builtin_ctz(mint::getmod() - 1);
mint e = mint(g).pow((mint::getmod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
// e^(2^i) == 1
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i <= cnt2 - 2; i++) {
sum_e2[i] = es[i] * now;
now *= ies[i];
}
now = 1;
for (int i = 0; i <= cnt2 - 3; i++) {
sum_e3[i] = es[i + 1] * now;
now *= ies[i + 1];
}
}
int len = 0;
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 *= sum_e2[__builtin_ctz(~(unsigned int)(s))];
}
len++;
} else {
int p = 1 << (h - len - 2);
mint rot = 1, imag = es[0];
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 a0 = a[i + offset];
auto a1 = a[i + offset + p] * rot;
auto a2 = a[i + offset + p * 2] * rot2;
auto a3 = a[i + offset + p * 3] * rot3;
auto a1na3imag = (a1 - a3) * imag;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + p] = a0 + a2 - a1 - a3;
a[i + offset + p * 2] = a0 - a2 + a1na3imag;
a[i + offset + p * 3] = a0 - a2 - a1na3imag;
}
if (s + 1 != (1 << len)) rot *= sum_e3[__builtin_ctz(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class FPS, class mint = typename FPS::value_type> void butterfly_inv(FPS &a) {
static constexpr int g = primitive_root<mint::getmod()>;
int n = int(a.size());
int h = 0;
while ((1U << h) < (unsigned int)(n)) h++;
static bool first = true;
static mint sum_ie2[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
static mint sum_ie3[30];
static mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
static mint invn[30];
if (first) {
first = false;
int cnt2 = __builtin_ctz(mint::getmod() - 1);
mint e = mint(g).pow((mint::getmod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
// e^(2^i) == 1
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i <= cnt2 - 2; i++) {
sum_ie2[i] = ies[i] * now;
now *= es[i];
}
now = 1;
for (int i = 0; i <= cnt2 - 3; i++) {
sum_ie3[i] = ies[i + 1] * now;
now *= es[i + 1];
}
invn[0] = 1;
invn[1] = mint::getmod() / 2 + 1;
for (int i = 2; i < 30; i++) invn[i] = invn[i - 1] * invn[1];
}
int len = h;
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] = (l - r) * irot;
}
if (s + 1 != (1 << (len - 1))) irot *= sum_ie2[__builtin_ctz(~(unsigned int)(s))];
}
len--;
} else {
int p = 1 << (h - len);
mint irot = 1, iimag = ies[0];
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 = a[i + offset];
auto a1 = a[i + offset + p];
auto a2 = a[i + offset + p * 2];
auto a3 = a[i + offset + p * 3];
auto a2na3iimag = (a2 - a3) * iimag;
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot;
a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2;
a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3;
}
if (s + 1 != (1 << (len - 2))) irot *= sum_ie3[__builtin_ctz(~(unsigned int)(s))];
}
len -= 2;
}
}
for (int i = 0; i < n; i++) a[i] *= invn[h];
}
template <class FPS, class mint = typename FPS::value_type> void doubling(FPS &a) {
int n = a.size();
auto b = a;
int z = 1;
butterfly_inv(b);
mint r = 1, zeta = mint(primitive_root<mint::getmod()>).pow((mint::getmod() - 1) / (n << 1));
for (int i = 0; i < n; i++) {
b[i] *= r;
r *= zeta;
}
butterfly(b);
std::copy(b.begin(), b.end(), std::back_inserter(a));
}
} // namespace kk2
#endif // KK2_MATH_MOD_BUTTERFLY_HPP
// #include "../math_mod/butterfly.hpp"
namespace kk2 {
template <class FPS, class mint = typename FPS::value_type> FPS convolution(FPS &a, const FPS &b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (std::min(n, m) <= 60) {
FPS res(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) { res[i + j] += a[i] * b[j]; }
}
a = res;
return a;
}
int z = 1;
while (z < n + m - 1) z <<= 1;
if (a == b) {
a.resize(z);
butterfly(a);
for (int i = 0; i < z; i++) a[i] *= a[i];
} else {
a.resize(z);
butterfly(a);
FPS t(b.begin(), b.end());
t.resize(z);
butterfly(t);
for (int i = 0; i < z; i++) a[i] *= t[i];
}
butterfly_inv(a);
a.resize(n + m - 1);
return a;
}
} // namespace kk2
#endif // KK2_CONVOLUTION_CONVOLUTION_HPP
// #include "../convolution/convolution.hpp"
#ifndef KK2_FPS_FPS_HPP
#define KK2_FPS_FPS_HPP 1
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <class mint> struct FormalPowerSeries : std::vector<mint> {
using std::vector<mint>::vector;
using FPS = FormalPowerSeries;
template <class OStream, is_ostream_t<OStream> * = nullptr> void display(OStream &os) const {
for (int i = 0; i < (int)this->size(); i++) {
os << (*this)[i] << " \n"[i == (int)this->size() - 1];
}
}
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &os) const {
for (int i = 0; i < (int)this->size(); i++) {
os << (*this)[i] << (i + 1 == (int)this->size() ? "\n" : " ");
}
}
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const FPS &fps_) {
for (int i = 0; i < (int)fps_.size(); i++) {
os << fps_[i] << (i + 1 == (int)fps_.size() ? "" : " ");
}
return os;
}
template <class IStream, is_istream_t<IStream> * = nullptr> FPS &input(IStream &is) {
for (int i = 0; i < (int)this->size(); i++) is >> (*this)[i];
return *this;
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, FPS &fps_) {
for (auto &x : fps_) is >> x;
return is;
}
FPS &operator+=(const FPS &r) {
if (this->size() < r.size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
return *this;
}
FPS &operator+=(const mint &r) {
if (this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
FPS &operator-=(const FPS &r) {
if (this->size() < r.size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
return *this;
}
FPS &operator-=(const mint &r) {
if (this->empty()) this->resize(1);
(*this)[0] -= r;
return *this;
}
FPS &operator*=(const mint &r) {
for (int i = 0; i < (int)this->size(); i++) { (*this)[i] *= r; }
return *this;
}
FPS &operator/=(const FPS &r) {
assert(!r.empty());
if (this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
if ((int)r.size() <= 64) {
FPS f(*this), g(r);
g.shrink();
mint coeff = g.back().inv();
for (auto &x : g) x *= coeff;
int deg = (int)f.size() - (int)g.size() + 1;
int gs = g.size();
FPS quo(deg);
for (int i = deg - 1; i >= 0; i--) {
quo[i] = f[i + gs - 1];
for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j];
}
*this = quo * coeff;
this->resize(n, mint(0));
return *this;
}
return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev();
}
FPS &operator%=(const FPS &r) {
*this -= *this / r * r;
shrink();
return *this;
}
FPS operator+(const FPS &r) const { return FPS(*this) += r; }
FPS operator+(const mint &r) const { return FPS(*this) += r; }
FPS operator-(const FPS &r) const { return FPS(*this) -= r; }
FPS operator-(const mint &r) const { return FPS(*this) -= r; }
FPS operator*(const mint &r) const { return FPS(*this) *= r; }
FPS operator/(const FPS &r) const { return FPS(*this) /= r; }
FPS operator%(const FPS &r) const { return FPS(*this) %= r; }
FPS operator-() const {
FPS ret(this->size());
for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
FPS shrink() {
while (this->size() && this->back() == mint(0)) this->pop_back();
return *this;
}
FPS rev() const {
FPS ret(*this);
std::reverse(ret.begin(), ret.end());
return ret;
}
FPS &inplace_rev() {
std::reverse(this->begin(), this->end());
return *this;
}
FPS dot(const FPS &r) const {
FPS ret(std::min(this->size(), r.size()));
for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i];
return ret;
}
FPS &inplace_dot(const FPS &r) {
this->resize(std::min(this->size(), r.size()));
for (int i = 0; i < (int)this->size(); i++) (*this)[i] *= r[i];
return *this;
}
FPS pre(int n) const {
FPS ret(this->begin(), this->begin() + std::min((int)this->size(), n));
if ((int)ret.size() < n) ret.resize(n, mint(0));
return ret;
}
FPS &inplace_pre(int n) {
this->resize(n);
return *this;
}
FPS operator>>(int n) const {
if (n >= (int)this->size()) return {};
FPS ret(this->begin() + n, this->end());
return ret;
}
FPS operator<<(int n) const {
FPS ret(*this);
ret.insert(ret.begin(), n, mint(0));
return ret;
}
FPS diff() const {
const int n = (int)this->size();
FPS ret(std::max(0, n - 1));
for (int i = 1; i < n; i++) { ret[i - 1] = (*this)[i] * mint(i); }
return ret;
}
FPS &inplace_diff() {
if (this->empty()) return *this = FPS();
this->erase(this->begin());
for (int i = 1; i <= (int)this->size(); i++) (*this)[i - 1] *= mint(i);
return *this;
}
FPS integral() const {
const int n = (int)this->size();
FPS ret(n + 1);
ret[0] = mint(0);
if (n > 0) ret[1] = mint(1);
auto mod = mint::getmod();
for (int i = 2; i <= n; i++) {
// p = q * i + r
// - q / r = 1 / i (mod p)
ret[i] = (-ret[mod % i]) * (mod / i);
}
for (int i = 0; i < n; i++) { ret[i + 1] *= (*this)[i]; }
return ret;
}
FPS &inplace_int() {
static std::vector<mint> inv{0, 1};
const int n = this->size();
auto mod = mint::getmod();
while ((int)inv.size() <= n) {
// p = q * i + r
// - q / r = 1 / i (mod p)
int i = inv.size();
inv.push_back((-inv[mod % i]) * (mod / i));
}
this->insert(this->begin(), mint(0));
for (int i = 1; i <= n; i++) (*this)[i] *= inv[i];
return *this;
}
mint eval(mint x) const {
mint r = 0, w = 1;
for (auto &v : *this) {
r += w * v;
w *= x;
}
return r;
}
FPS log(int deg = -1) const {
assert(!this->empty() && (*this)[0] == mint(1));
if (deg == -1) deg = this->size();
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
FPS sparse_log(int deg = -1) const {
assert(!this->empty() && (*this)[0] == mint(1));
if (deg == -1) deg = this->size();
std::vector<std::pair<int, mint>> fs;
for (int i = 1; i < int(this->size()); i++) {
if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);
}
int mod = mint::getmod();
static std::vector<mint> inv{1, 1};
while ((int)inv.size() <= deg) {
int i = inv.size();
inv.push_back(-inv[mod % i] * (mod / i));
}
FPS g(deg);
for (int k = 0; k < deg - 1; k++) {
for (auto &[j, fj] : fs) {
if (k < j) break;
int i = k - j;
g[k + 1] -= g[i + 1] * fj * (i + 1);
}
g[k + 1] *= inv[k + 1];
if (k + 1 < int(this->size())) g[k + 1] += (*this)[k + 1];
}
return g;
}
template <class T> FPS pow(T k, int deg = -1) const {
const int n = this->size();
if (deg == -1) deg = n;
if (k == 0) {
FPS ret(deg);
if (deg > 0) ret[0] = mint(1);
return ret;
}
for (int i = 0; i < n; i++) {
if ((*this)[i] != mint(0)) {
mint rev = mint(1) / (*this)[i];
FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);
ret *= (*this)[i].pow(k);
ret = (ret << (i * k)).pre(deg);
if ((int)ret.size() < deg) ret.resize(deg, mint(0));
return ret;
}
if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));
}
return FPS(deg, mint(0));
}
template <class T> FPS sparse_pow(T k, int deg = -1) const {
if (deg == -1) deg = this->size();
if (k == 0) {
FPS ret(deg);
if (deg > 0) ret[0] = mint(1);
return ret;
}
int zero = 0;
while (zero != int(this->size()) && (*this)[zero] == mint(0)) zero++;
if (zero == int(this->size()) || __int128_t(zero) * k >= deg) { return FPS(deg, mint(0)); }
if (zero != 0) {
FPS suf(this->begin() + zero, this->end());
auto g = suf.sparse_pow(k, deg - zero * k);
FPS ret(zero * k, mint(0));
std::copy(std::begin(g), std::end(g), std::back_inserter(ret));
return ret;
}
int mod = mint::getmod();
static std::vector<mint> inv{1, 1};
while ((int)inv.size() <= deg) {
int i = inv.size();
inv.push_back(-inv[mod % i] * (mod / i));
}
std::vector<std::pair<int, mint>> fs;
for (int i = 1; i < int(this->size()); i++) {
if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);
}
FPS g(deg);
g[0] = (*this)[0].pow(k);
mint denom = (*this)[0].inv();
k %= mod;
for (int a = 1; a < deg; a++) {
for (auto &[i, f_i] : fs) {
if (a < i) break;
g[a] += g[a - i] * f_i * (mint(i) * (k + 1) - a);
}
g[a] *= denom * inv[a];
}
return g;
}
// assume that r is sparse
// return this / r
FPS sparse_div(const FPS &r, int deg = -1) const {
assert(!r.empty() && r[0] != mint(0));
if (deg == -1) deg = this->size();
mint ir0 = r[0].inv();
FPS ret = *this * ir0;
ret.resize(deg);
std::vector<std::pair<int, mint>> gs;
for (int i = 1; i < (int)r.size(); i++) {
if (r[i] != mint(0)) gs.emplace_back(i, r[i] * ir0);
}
for (int i = 0; i < deg; i++) {
for (auto &[j, g_j] : gs) {
if (i + j >= deg) break;
ret[i + j] -= ret[i] * g_j;
}
}
return ret;
}
FPS sparse_inv(int deg = -1) const {
assert(!this->empty() && (*this)[0] != mint(0));
if (deg == -1) deg = this->size();
std::vector<std::pair<int, mint>> fs;
for (int i = 1; i < int(this->size()); i++) {
if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);
}
FPS ret(deg);
mint if0 = (*this)[0].inv();
if (0 < deg) ret[0] = if0;
for (int k = 1; k < deg; k++) {
for (auto &[j, fj] : fs) {
if (k < j) break;
ret[k] += ret[k - j] * fj;
}
ret[k] *= -if0;
}
return ret;
}
FPS sparse_exp(int deg = -1) const {
assert(this->empty() || (*this)[0] == mint(0));
if (deg == -1) deg = this->size();
std::vector<std::pair<int, mint>> fs;
for (int i = 1; i < int(this->size()); i++) {
if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);
}
int mod = mint::getmod();
static std::vector<mint> inv{1, 1};
while ((int)inv.size() <= deg) {
int i = inv.size();
inv.push_back(-inv[mod % i] * (mod / i));
}
FPS g(deg);
if (deg) g[0] = 1;
for (int k = 0; k < deg - 1; k++) {
for (auto &[ip1, fip1] : fs) {
int i = ip1 - 1;
if (k < i) break;
g[k + 1] += g[k - i] * fip1 * (i + 1);
}
g[k + 1] *= inv[k + 1];
}
return g;
}
FPS &inplace_imos(int n) {
inplace_pre(n);
for (int i = 0; i < n - 1; i++) { (*this)[i + 1] += (*this)[i]; }
return *this;
}
FPS imos(int n) const {
FPS ret(*this);
return ret.inplace_imos(n);
}
FPS &inplace_iimos(int n) {
inplace_pre(n);
for (int i = 0; i < n - 1; i++) { (*this)[i + 1] -= (*this)[i]; }
return *this;
}
FPS iimos(int n) const {
FPS ret(*this);
return ret.inplace_iimos(n);
}
FPS &operator*=(const FPS &r);
FPS operator*(const FPS &r) const { return FPS(*this) *= r; }
void but();
void ibut();
void db();
static int but_pr();
FPS inv(int deg = -1) const;
FPS exp(int deg = -1) const;
};
} // namespace kk2
#endif // KK2_FPS_FPS_HPP
// #include "fps.hpp"
namespace kk2 {
template <class mint>
FormalPowerSeries<mint> &FormalPowerSeries<mint>::operator*=(const FormalPowerSeries<mint> &r) {
if (this->empty() || r.empty()) {
this->clear();
return *this;
}
convolution(*this, r);
return *this;
}
template <class mint> void FormalPowerSeries<mint>::but() {
butterfly(*this);
}
template <class mint> void FormalPowerSeries<mint>::ibut() {
butterfly_inv(*this);
}
template <class mint> void FormalPowerSeries<mint>::db() {
doubling(*this);
}
template <class mint> int FormalPowerSeries<mint>::but_pr() {
return primitive_root<mint::getmod()>;
}
template <class mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::inv(int deg) const {
assert((*this)[0] != mint(0));
if (deg == -1) deg = (int)this->size();
FormalPowerSeries<mint> res(deg);
res[0] = {mint(1) / (*this)[0]};
for (int d = 1; d < deg; d <<= 1) {
FormalPowerSeries<mint> f(2 * d), g(2 * d);
std::copy(std::begin(*this),
std::begin(*this) + std::min((int)this->size(), 2 * d),
std::begin(f));
std::copy(std::begin(res), std::begin(res) + d, std::begin(g));
f.but();
g.but();
f.inplace_dot(g);
f.ibut();
std::fill(std::begin(f), std::begin(f) + d, mint(0));
f.but();
f.inplace_dot(g);
f.ibut();
for (int j = d; j < std::min(2 * d, deg); j++) res[j] = -f[j];
}
return res.pre(deg);
}
template <class mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::exp(int deg) const {
assert(this->empty() || (*this)[0] == mint(0));
if (deg == -1) deg = (int)this->size();
FormalPowerSeries<mint> inv;
inv.reserve(deg + 1);
inv.push_back(mint(0));
inv.push_back(mint(1));
FormalPowerSeries<mint> b{1, 1 < (int)this->size() ? (*this)[1] : mint(0)};
FormalPowerSeries<mint> c{1}, z1, z2{1, 1};
for (int m = 2; m < deg; m <<= 1) {
auto y = b;
y.resize(m << 1);
y.but();
z1 = z2;
FormalPowerSeries<mint> z(m);
z = y.dot(z1);
z.ibut();
std::fill(std::begin(z), std::begin(z) + (m >> 1), mint(0));
z.but();
z.inplace_dot(-z1);
z.ibut();
c.insert(std::end(c), std::begin(z) + (m >> 1), std::end(z));
z2 = c;
z2.resize(m << 1);
z2.but();
FormalPowerSeries<mint> x(this->begin(), this->begin() + std::min<int>(this->size(), m));
x.resize(m);
x.inplace_diff();
x.push_back(mint(0));
x.but();
x.inplace_dot(y);
x.ibut();
x -= b.diff();
x.resize(m << 1);
for (int i = 0; i < m - 1; i++) {
x[m + i] = x[i];
x[i] = mint(0);
}
x.but();
x.inplace_dot(z2);
x.ibut();
x.pop_back();
x.inplace_int();
for (int i = m; i < std::min<int>(this->size(), m << 1); i++) x[i] += (*this)[i];
std::fill(std::begin(x), std::begin(x) + m, mint(0));
x.but();
x.inplace_dot(y);
x.ibut();
b.insert(std::end(b), std::begin(x) + m, std::end(x));
}
return FormalPowerSeries<mint>(std::begin(b), std::begin(b) + deg);
}
} // namespace kk2
#endif // KK2_FPS_NTT_FRIENDLY_HPP
// #include <kk2/fps/ntt_friendly.hpp>
#ifndef KK2_FPS_POLY_TAYLOR_SHIFT_HPP
#define KK2_FPS_POLY_TAYLOR_SHIFT_HPP 1
#include <algorithm>
#ifndef KK2_MATH_MOD_COMB_HPP
#define KK2_MATH_MOD_COMB_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <class mint> struct Comb {
static inline std::vector<mint> _fact{1}, _ifact{1}, _inv{1};
Comb() = delete;
static void extend(int m = -1) {
int n = (int)_fact.size();
if (m == -1) m = n << 1;
if (n > m) return;
m = std::min<int>(m, mint::getmod() - 1);
_fact.resize(m + 1);
_ifact.resize(m + 1);
_inv.resize(m + 1);
for (int i = n; i <= m; i++) _fact[i] = _fact[i - 1] * i;
_ifact[m] = _fact[m].inv();
_inv[m] = _ifact[m] * _fact[m - 1];
for (int i = m; i > n; i--) {
_ifact[i - 1] = _ifact[i] * i;
_inv[i - 1] = _ifact[i - 1] * _fact[i - 2];
}
}
static mint fact(int n) {
if (n < 0) return 0;
if ((int)_fact.size() <= n) extend(n);
return _fact[n];
}
static mint ifact(int n) {
if (n < 0) return 0;
if ((int)_ifact.size() <= n) extend(n);
return _ifact[n];
}
static mint inv(int n) {
if (n < 0) return -inv(-n);
if ((int)_inv.size() <= n) extend(n);
return _inv[n];
}
static mint binom(int n, int k) {
if (k < 0 || k > n) return 0;
return fact(n) * ifact(k) * ifact(n - k);
}
template <class T> static mint multinomial(const std::vector<T> &r) {
static_assert(is_integral<T>::value, "T must be integral");
int n = 0;
for (auto &x : r) {
if (x < 0) return 0;
n += x;
}
mint res = fact(n);
for (auto &x : r) res *= ifact(x);
return res;
}
static mint binom_naive(int n, int k) {
if (n < 0 || k < 0 || k > n) return 0;
mint res = 1;
k = std::min(k, n - k);
for (int i = 1; i <= k; i++) res *= inv(i) * (n--);
return res;
}
static mint permu(int n, int k) {
if (n < 0 || k < 0 || k > n) return 0;
return fact(n) * ifact(n - k);
}
static mint homo(int n, int k) {
if (n < 0 || k < 0) return 0;
return k == 0 ? 1 : binom(n + k - 1, k);
}
};
} // namespace kk2
#endif // KK2_MATH_MOD_COMB_HPP
// #include "../math_mod/comb.hpp"
namespace kk2 {
template <class FPS, class mint = typename FPS::value_type>
FPS taylor_shift(const FPS &f_, mint a) {
FPS f(f_);
int n = f.size();
Comb<mint>::extend(n);
for (int i = 0; i < n; i++) f[i] *= Comb<mint>::fact(i);
f.inplace_rev();
FPS g(n, mint(1));
for (int i = 1; i < n; i++) g[i] = g[i - 1] * a * Comb<mint>::inv(i);
f = (f * g).pre(n).rev();
for (int i = 0; i < n; i++) f[i] *= Comb<mint>::ifact(i);
return f;
}
} // namespace kk2
#endif // KK2_FPS_POLY_TAYLOR_SHIFT_HPP
// #include <kk2/fps/poly_taylor_shift.hpp>
#ifndef KK2_MODINT_MONT_HPP
#define KK2_MODINT_MONT_HPP 1
#include <cassert>
#include <cstdint>
#include <iostream>
#include <type_traits>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <int p> struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = p;
for (int i = 0; i < 4; ++i) ret *= 2 - p * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(p) % p;
static_assert(r * p == 1, "invalid, r * p != 1");
static_assert(p < (1 << 30), "invalid, p >= 2 ^ 30");
static_assert((p & 1) == 1, "invalid, p % 2 == 0");
u32 _v;
constexpr LazyMontgomeryModInt() : _v(0) {}
template <typename T, is_integral_t<T> * = nullptr>
constexpr LazyMontgomeryModInt(T b) : _v(reduce(u64(b % p + p) * n2)) {}
static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * p) >> 32; }
constexpr mint &operator++() { return *this += 1; }
constexpr mint &operator--() { return *this -= 1; }
constexpr mint operator++(int) {
mint ret = *this;
*this += 1;
return ret;
}
constexpr mint operator--(int) {
mint ret = *this;
*this -= 1;
return ret;
}
constexpr mint &operator+=(const mint &b) {
if (i32(_v += b._v - 2 * p) < 0) _v += 2 * p;
return *this;
}
constexpr mint &operator-=(const mint &b) {
if (i32(_v -= b._v) < 0) _v += 2 * p;
return *this;
}
constexpr mint &operator*=(const mint &b) {
_v = reduce(u64(_v) * b._v);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inv();
return *this;
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr bool operator==(const mint &b) const {
return (_v >= p ? _v - p : _v) == (b._v >= p ? b._v - p : b._v);
}
constexpr bool operator!=(const mint &b) const {
return (_v >= p ? _v - p : _v) != (b._v >= p ? b._v - p : b._v);
}
friend constexpr mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
friend constexpr mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
friend constexpr mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
friend constexpr mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
template <class T> constexpr mint pow(T n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inv() const { return pow(p - 2); }
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const mint &x) {
return os << x.val();
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, mint &x) {
i64 t;
is >> t;
x = mint(t);
return (is);
}
constexpr u32 val() const {
u32 ret = reduce(_v);
return ret >= p ? ret - p : ret;
}
static constexpr u32 getmod() { return p; }
};
template <int p> using Mont = LazyMontgomeryModInt<p>;
using mont998 = Mont<998244353>;
using mont107 = Mont<1000000007>;
} // namespace kk2
#endif // KK2_MODINT_MONT_HPP
// #include <kk2/modint/mont.hpp>
// #include <kk2/math_mod/comb.hpp>
using namespace std;
using FPS = kk2::FormalPowerSeries<kk2::mont998>;
void solve() {
int n;
kin >> n;
vc<int> a(n);
kin >> a;
sort(all(a));
vc<pair<kk2::mont998, int>> b;
for (auto x : a) {
if (b.empty() || b.back().first != kk2::mont998(x)) {
b.emplace_back(x, 1);
} else {
b.back().second++;
}
}
vc<FPS> mono(b.size());
rep (i, b.size()) mono[i] = FPS{b[i].first.pow(2), 1}.pow(b[i].second, b[i].second + 1);
FPS all{1};
vc<FPS> c(b.size());
rep (i, b.size()) all *= mono[i];
rep (i, b.size()) {
FPS h = all / mono[i];
// by constrainsts, if a[i] != a[j], a[i]^2 != a[j]^2 mod 998244353
// so, [x^0]h(x - b[i].first^2) != 0
c[i] = kk2::taylor_shift(h, -b[i].first.pow(2)).inv(b[i].second);
}
kk2::mont998 res = 0;
rep (i, b.size()) {
rep (j, c[i].size()) {
int m = b[i].second - j;
res += c[i][j] *
kk2::Comb<kk2::mont998>::binom(2 * m - 2, m - 1) *
b[i].first.pow(2 * m - 1).inv() *
kk2::mont998(2).pow(2 * m - 2).inv();
}
}
kout << res << kendl;
}
int main() {
int t = 1;
// kin >> t;
rep (t) solve();
return 0;
}
// converted!!
// Author: kk2
// 2025-01-06 21:51:09