結果
問題 | No.2798 Multiple Chain |
ユーザー | ruthen71 |
提出日時 | 2024-06-28 22:43:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 28,242 bytes |
コンパイル時間 | 2,805 ms |
コンパイル使用メモリ | 181,684 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 22:43:51 |
合計ジャッジ時間 | 3,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 5 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 6 ms
5,376 KB |
testcase_17 | AC | 8 ms
5,376 KB |
testcase_18 | AC | 6 ms
5,376 KB |
testcase_19 | AC | 6 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 5 ms
5,376 KB |
testcase_26 | AC | 4 ms
5,376 KB |
testcase_27 | AC | 5 ms
5,376 KB |
testcase_28 | AC | 4 ms
5,376 KB |
testcase_29 | AC | 3 ms
5,376 KB |
testcase_30 | AC | 3 ms
5,376 KB |
testcase_31 | AC | 3 ms
5,376 KB |
testcase_32 | AC | 3 ms
5,376 KB |
testcase_33 | AC | 3 ms
5,376 KB |
testcase_34 | AC | 3 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 3 ms
5,376 KB |
testcase_41 | AC | 3 ms
5,376 KB |
testcase_42 | AC | 3 ms
5,376 KB |
testcase_43 | AC | 3 ms
5,376 KB |
testcase_44 | AC | 3 ms
5,376 KB |
testcase_45 | AC | 3 ms
5,376 KB |
testcase_46 | AC | 3 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 3 ms
5,376 KB |
testcase_49 | AC | 3 ms
5,376 KB |
testcase_50 | AC | 3 ms
5,376 KB |
testcase_51 | AC | 3 ms
5,376 KB |
testcase_52 | AC | 3 ms
5,376 KB |
testcase_53 | AC | 4 ms
5,376 KB |
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <deque> #include <forward_list> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <list> #include <map> #include <memory> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #ifdef RUTHEN_LOCAL #include <debug.hpp> #else #define show(x) true #endif // type definition using i64 = long long; using u32 = unsigned int; using u64 = unsigned long long; using f32 = float; using f64 = double; using f128 = long double; template <class T> using pque = std::priority_queue<T>; template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>; // overload #define overload4(_1, _2, _3, _4, name, ...) name #define overload3(_1, _2, _3, name, ...) name #define overload2(_1, _2, name, ...) name // for loop #define REP1(a) for (long long _ = 0; _ < (a); _++) #define REP2(i, a) for (long long i = 0; i < (a); i++) #define REP3(i, a, b) for (long long i = (a); i < (b); i++) #define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c)) #define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define RREP1(a) for (long long _ = (a)-1; _ >= 0; _--) #define RREP2(i, a) for (long long i = (a)-1; i >= 0; i--) #define RREP3(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__) #define FORE1(x, a) for (auto &&x : a) #define FORE2(x, y, a) for (auto &&[x, y] : a) #define FORE3(x, y, z, a) for (auto &&[x, y, z] : a) #define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__) #define FORSUB(t, s) for (long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) // function #define ALL(a) (a).begin(), (a).end() #define RALL(a) (a).rbegin(), (a).rend() #define SORT(a) std::sort((a).begin(), (a).end()) #define RSORT(a) std::sort((a).rbegin(), (a).rend()) #define REV(a) std::reverse((a).begin(), (a).end()) #define UNIQUE(a) \ std::sort((a).begin(), (a).end()); \ (a).erase(std::unique((a).begin(), (a).end()), (a).end()) #define LEN(a) (int)((a).size()) #define MIN(a) *std::min_element((a).begin(), (a).end()) #define MAX(a) *std::max_element((a).begin(), (a).end()) #define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL) #define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x)) #define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__) #define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x))) #define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x))) template <class T, class U> inline bool chmin(T &a, const U &b) { return (a > T(b) ? a = b, 1 : 0); } template <class T, class U> inline bool chmax(T &a, const U &b) { return (a < T(b) ? a = b, 1 : 0); } template <class T, class S> inline T floor(const T x, const S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1))); } template <class T, class S> inline T ceil(const T x, const S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) { T q = floor(x, y); return {q, x - q * y}; } // 10 ^ n constexpr long long TEN(int n) { return (n == 0) ? 1 : 10LL * TEN(n - 1); } // 1 + 2 + ... + n #define TRI1(n) ((n) * ((n) + 1LL) / 2) // l + (l + 1) + ... + r #define TRI2(l, r) (((l) + (r)) * ((r) - (l) + 1LL) / 2) #define TRI(...) overload2(__VA_ARGS__, TRI2, TRI1)(__VA_ARGS__) // bit operation // bit[i] (= 0 or 1) #define IBIT(bit, i) (((bit) >> (i)) & 1) // (0, 1, 2, 3, 4) -> (0, 1, 3, 7, 15) #define MASK(n) ((1LL << (n)) - 1) #define POW2(n) (1LL << (n)) // (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1) int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(i64 x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } // binary search template <class T, class F> T bin_search(T ok, T ng, F &f) { while ((ok > ng ? ok - ng : ng - ok) > 1) { T md = (ng + ok) >> 1; (f(md) ? ok : ng) = md; } return ok; } template <class T, class F> T bin_search_real(T ok, T ng, F &f, const int iter = 100) { for (int _ = 0; _ < iter; _++) { T md = (ng + ok) / 2; (f(md) ? ok : ng) = md; } return ok; } // rotate matrix counterclockwise by pi / 2 template <class T> void rot(std::vector<std::vector<T>> &a) { if ((int)(a.size()) == 0) return; if ((int)(a[0].size()) == 0) return; int n = (int)(a.size()), m = (int)(a[0].size()); std::vector res(m, std::vector<T>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { res[m - 1 - j][i] = a[i][j]; } } a.swap(res); } // const value constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; // infinity template <class T> constexpr T INF = 0; template <> constexpr int INF<int> = 1'000'000'000; // 1e9 template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2; // 2e18 template <> constexpr u32 INF<u32> = INF<int>; // 1e9 template <> constexpr u64 INF<u64> = INF<i64>; // 2e18 template <> constexpr f32 INF<f32> = INF<i64>; // 2e18 template <> constexpr f64 INF<f64> = INF<i64>; // 2e18 template <> constexpr f128 INF<f128> = INF<i64>; // 2e18 // I/O // input template <class T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (auto &&i : v) is >> i; return is; } template <class... T> void in(T &...a) { (std::cin >> ... >> a); } void scan() {} template <class Head, class... Tail> void scan(Head &head, Tail &...tail) { in(head); scan(tail...); } // input macro #define INT(...) \ int __VA_ARGS__; \ scan(__VA_ARGS__) #define I64(...) \ i64 __VA_ARGS__; \ scan(__VA_ARGS__) #define U32(...) \ u32 __VA_ARGS__; \ scan(__VA_ARGS__) #define U64(...) \ u64 __VA_ARGS__; \ scan(__VA_ARGS__) #define F32(...) \ f32 __VA_ARGS__; \ scan(__VA_ARGS__) #define F64(...) \ f64 __VA_ARGS__; \ scan(__VA_ARGS__) #define F128(...) \ f128 __VA_ARGS__; \ scan(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ scan(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ scan(__VA_ARGS__) #define VEC(type, name, size) \ std::vector<type> name(size); \ scan(name) #define VEC2(type, name1, name2, size) \ std::vector<type> name1(size), name2(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i]) #define VEC3(type, name1, name2, name3, size) \ std::vector<type> name1(size), name2(size), name3(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i]) #define VEC4(type, name1, name2, name3, name4, size) \ std::vector<type> name1(size), name2(size), name3(size), name4(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i]) #define VV(type, name, h, w) \ std::vector name((h), std::vector<type>((w))); \ scan(name) // output template <class T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) { auto n = v.size(); for (size_t i = 0; i < n; i++) { if (i) os << ' '; os << v[i]; } return os; } template <class... T> void out(const T &...a) { (std::cout << ... << a); } void print() { out('\n'); } template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) { out(head); if (sizeof...(Tail)) out(' '); print(tail...); } // for interactive problems void printi() { std::cout << std::endl; } template <class Head, class... Tail> void printi(Head &&head, Tail &&...tail) { out(head); if (sizeof...(Tail)) out(' '); printi(tail...); } // bool output void YES(bool t = 1) { print(t ? "YES" : "NO"); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void NO(bool t = 1) { YES(!t); } void No(bool t = 1) { Yes(!t); } void no(bool t = 1) { yes(!t); } void POSSIBLE(bool t = 1) { print(t ? "POSSIBLE" : "IMPOSSIBLE"); } void Possible(bool t = 1) { print(t ? "Possible" : "Impossible"); } void possible(bool t = 1) { print(t ? "possible" : "impossible"); } void IMPOSSIBLE(bool t = 1) { POSSIBLE(!t); } void Impossible(bool t = 1) { Possible(!t); } void impossible(bool t = 1) { possible(!t); } void FIRST(bool t = 1) { print(t ? "FIRST" : "SECOND"); } void First(bool t = 1) { print(t ? "First" : "Second"); } void first(bool t = 1) { print(t ? "first" : "second"); } void SECOND(bool t = 1) { FIRST(!t); } void Second(bool t = 1) { First(!t); } void second(bool t = 1) { first(!t); } // I/O speed up struct SetUpIO { SetUpIO() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout << std::fixed << std::setprecision(15); } } set_up_io; using namespace std; // https://nyaannyaan.github.io/library/prime/fast-factorize.hpp #include <cstdint> using namespace std; using namespace std; namespace internal { template <typename T> using is_broadly_integral = typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> || is_same_v<T, __uint128_t>, true_type, false_type>::type; template <typename T> using is_broadly_signed = typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>, true_type, false_type>::type; template <typename T> using is_broadly_unsigned = typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>, true_type, false_type>::type; #define ENABLE_VALUE(x) template <typename T> constexpr bool x##_v = x<T>::value; ENABLE_VALUE(is_broadly_integral); ENABLE_VALUE(is_broadly_signed); ENABLE_VALUE(is_broadly_unsigned); #undef ENABLE_VALUE #define ENABLE_HAS_TYPE(var) \ template <class, class = void> struct has_##var : false_type {}; \ template <class T> struct has_##var<T, void_t<typename T::var>> : true_type {}; \ template <class T> constexpr auto has_##var##_v = has_##var<T>::value; #define ENABLE_HAS_VAR(var) \ template <class, class = void> struct has_##var : false_type {}; \ template <class T> struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \ template <class T> constexpr auto has_##var##_v = has_##var<T>::value; } // namespace internal namespace internal { using namespace std; // a mod p template <typename T> T safe_mod(T a, T p) { a %= p; if constexpr (is_broadly_signed_v<T>) { if (a < 0) a += p; } return a; } // 返り値:pair(g, x) // s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g template <typename T> pair<T, T> inv_gcd(T a, T p) { static_assert(is_broadly_signed_v<T>); a = safe_mod(a, p); if (a == 0) return {p, 0}; T b = p, x = 1, y = 0; while (a != 0) { T q = b / a; swap(a, b %= a); swap(x, y -= q * x); } if (y < 0) y += p / b; return {b, y}; } // 返り値 : a^{-1} mod p // gcd(a, p) != 1 が必要 template <typename T> T inv(T a, T p) { static_assert(is_broadly_signed_v<T>); a = safe_mod(a, p); T b = p, x = 1, y = 0; while (a != 0) { T q = b / a; swap(a, b %= a); swap(x, y -= q * x); } assert(b == 1); return y < 0 ? y + p : y; } // T : 底の型 // U : T*T がオーバーフローしない かつ 指数の型 template <typename T, typename U> T modpow(T a, U n, T p) { a = safe_mod(a, p); T ret = 1 % p; while (n != 0) { if (n % 2 == 1) ret = U(ret) * a % p; a = U(a) * a % p; n /= 2; } return ret; } // 返り値 : pair(rem, mod) // 解なしのときは {0, 0} を返す template <typename T> pair<T, T> crt(const vector<T> &r, const vector<T> &m) { static_assert(is_broadly_signed_v<T>); assert(r.size() == m.size()); int n = int(r.size()); T r0 = 0, m0 = 1; for (int i = 0; i < n; i++) { assert(1 <= m[i]); T r1 = safe_mod(r[i], m[i]), m1 = m[i]; if (m0 < m1) swap(r0, r1), swap(m0, m1); if (m0 % m1 == 0) { if (r0 % m1 != r1) return {0, 0}; continue; } auto [g, im] = inv_gcd(m0, m1); T u1 = m1 / g; if ((r1 - r0) % g) return {0, 0}; T x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; } return {r0, m0}; } } // namespace internal using namespace std; namespace internal { unsigned long long non_deterministic_seed() { unsigned long long m = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(); m ^= 9845834732710364265uLL; m ^= m << 24, m ^= m >> 31, m ^= m << 35; return m; } unsigned long long deterministic_seed() { return 88172645463325252UL; } // 64 bit の seed 値を生成 (手元では seed 固定) // 連続で呼び出すと同じ値が何度も返ってくるので注意 // #define RANDOMIZED_SEED するとシードがランダムになる unsigned long long seed() { #if defined(NyaanLocal) && !defined(RANDOMIZED_SEED) return deterministic_seed(); #else return non_deterministic_seed(); #endif } } // namespace internal namespace my_rand { using i64 = long long; using u64 = unsigned long long; // [0, 2^64 - 1) u64 rng() { static u64 _x = internal::seed(); return _x ^= _x << 7, _x ^= _x >> 9; } // [l, r] i64 rng(i64 l, i64 r) { assert(l <= r); return l + rng() % u64(r - l + 1); } // [l, r) i64 randint(i64 l, i64 r) { assert(l < r); return l + rng() % u64(r - l); } // choose n numbers from [l, r) without overlapping vector<i64> randset(i64 l, i64 r, i64 n) { assert(l <= r && n <= r - l); unordered_set<i64> s; for (i64 i = n; i; --i) { i64 m = randint(l, r + 1 - i); if (s.find(m) != s.end()) m = r - i; s.insert(m); } vector<i64> ret; for (auto &x : s) ret.push_back(x); sort(begin(ret), end(ret)); return ret; } // [0.0, 1.0) double rnd() { return rng() * 5.42101086242752217004e-20; } // [l, r) double rnd(double l, double r) { assert(l < r); return l + rnd() * (r - l); } template <typename T> void randshf(vector<T> &v) { int n = v.size(); for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]); } } // namespace my_rand using my_rand::randint; using my_rand::randset; using my_rand::randshf; using my_rand::rnd; using my_rand::rng; using namespace std; template <typename Int, typename UInt, typename Long, typename ULong, int id> struct ArbitraryLazyMontgomeryModIntBase { using mint = ArbitraryLazyMontgomeryModIntBase; inline static UInt mod; inline static UInt r; inline static UInt n2; static constexpr int bit_length = sizeof(UInt) * 8; static UInt get_r() { UInt ret = mod; while (mod * ret != 1) ret *= UInt(2) - mod * ret; return ret; } static void set_mod(UInt m) { assert(m < (UInt(1u) << (bit_length - 2))); assert((m & 1) == 1); mod = m, n2 = -ULong(m) % m, r = get_r(); } UInt a; ArbitraryLazyMontgomeryModIntBase() : a(0) {} ArbitraryLazyMontgomeryModIntBase(const Long &b) : a(reduce(ULong(b % mod + mod) * n2)){}; static UInt reduce(const ULong &b) { return (b + ULong(UInt(b) * UInt(-r)) * mod) >> bit_length; } mint &operator+=(const mint &b) { if (Int(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } mint &operator-=(const mint &b) { if (Int(a -= b.a) < 0) a += 2 * mod; return *this; } mint &operator*=(const mint &b) { a = reduce(ULong(a) * b.a); return *this; } mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } mint operator+(const mint &b) const { return mint(*this) += b; } mint operator-(const mint &b) const { return mint(*this) -= b; } mint operator*(const mint &b) const { return mint(*this) *= b; } mint operator/(const mint &b) const { return mint(*this) /= b; } bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } mint operator-() const { return mint(0) - mint(*this); } mint operator+() const { return mint(*this); } mint pow(ULong n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { Long t; is >> t; b = ArbitraryLazyMontgomeryModIntBase(t); return (is); } mint inverse() const { Int x = get(), y = get_mod(), u = 1, v = 0; while (y > 0) { Int t = x / y; swap(x -= t * y, y); swap(u -= t * v, v); } return mint{u}; } UInt get() const { UInt ret = reduce(a); return ret >= mod ? ret - mod : ret; } static UInt get_mod() { return mod; } }; // id に適当な乱数を割り当てて使う template <int id> using ArbitraryLazyMontgomeryModInt = ArbitraryLazyMontgomeryModIntBase<int, unsigned int, long long, unsigned long long, id>; template <int id> using ArbitraryLazyMontgomeryModInt64bit = ArbitraryLazyMontgomeryModIntBase<long long, unsigned long long, __int128_t, __uint128_t, id>; using namespace std; namespace fast_factorize { template <typename T, typename U> bool miller_rabin(const T &n, vector<T> ws) { if (n <= 2) return n == 2; if (n % 2 == 0) return false; T d = n - 1; while (d % 2 == 0) d /= 2; U e = 1, rev = n - 1; for (T w : ws) { if (w % n == 0) continue; T t = d; U y = internal::modpow<T, U>(w, t, n); while (t != n - 1 && y != e && y != rev) y = y * y % n, t *= 2; if (y != rev && t % 2 == 0) return false; } return true; } bool miller_rabin_u64(unsigned long long n) { return miller_rabin<unsigned long long, __uint128_t>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } template <typename mint> bool miller_rabin(unsigned long long n, vector<unsigned long long> ws) { if (n <= 2) return n == 2; if (n % 2 == 0) return false; if (mint::get_mod() != n) mint::set_mod(n); unsigned long long d = n - 1; while (~d & 1) d >>= 1; mint e = 1, rev = n - 1; for (unsigned long long w : ws) { if (w % n == 0) continue; unsigned long long t = d; mint y = mint(w).pow(t); while (t != n - 1 && y != e && y != rev) y *= y, t *= 2; if (y != rev && t % 2 == 0) return false; } return true; } bool is_prime(unsigned long long n) { using mint32 = ArbitraryLazyMontgomeryModInt<96229631>; using mint64 = ArbitraryLazyMontgomeryModInt64bit<622196072>; if (n <= 2) return n == 2; if (n % 2 == 0) return false; if (n < (1uLL << 30)) { return miller_rabin<mint32>(n, {2, 7, 61}); } else if (n < (1uLL << 62)) { return miller_rabin<mint64>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } else { return miller_rabin_u64(n); } } } // namespace fast_factorize using fast_factorize::is_prime; /** * @brief Miller-Rabin primality test */ namespace fast_factorize { using u64 = uint64_t; template <typename mint, typename T> T pollard_rho(T n) { if (~n & 1) return 2; if (is_prime(n)) return n; if (mint::get_mod() != n) mint::set_mod(n); mint R, one = 1; auto f = [&](mint x) { return x * x + R; }; auto rnd_ = [&]() { return rng() % (n - 2) + 2; }; while (1) { mint x, y, ys, q = one; R = rnd_(), y = rnd_(); T g = 1; constexpr int m = 128; for (int r = 1; g == 1; r <<= 1) { x = y; for (int i = 0; i < r; ++i) y = f(y); for (int k = 0; g == 1 && k < r; k += m) { ys = y; for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y)); g = gcd(q.get(), n); } } if (g == n) do g = gcd((x - (ys = f(ys))).get(), n); while (g == 1); if (g != n) return g; } exit(1); } using i64 = long long; vector<i64> inner_factorize(u64 n) { using mint32 = ArbitraryLazyMontgomeryModInt<452288976>; using mint64 = ArbitraryLazyMontgomeryModInt64bit<401243123>; if (n <= 1) return {}; u64 p; if (n <= (1LL << 30)) { p = pollard_rho<mint32, uint32_t>(n); } else if (n <= (1LL << 62)) { p = pollard_rho<mint64, uint64_t>(n); } else { exit(1); } if (p == n) return {i64(p)}; auto l = inner_factorize(p); auto r = inner_factorize(n / p); copy(begin(r), end(r), back_inserter(l)); return l; } vector<i64> factorize(u64 n) { auto ret = inner_factorize(n); sort(begin(ret), end(ret)); return ret; } map<i64, i64> factor_count(u64 n) { map<i64, i64> mp; for (auto &x : factorize(n)) mp[x]++; return mp; } vector<i64> divisors(u64 n) { if (n == 0) return {}; vector<pair<i64, i64>> v; for (auto &p : factorize(n)) { if (v.empty() || v.back().first != p) { v.emplace_back(p, 1); } else { v.back().second++; } } vector<i64> ret; auto f = [&](auto rc, int i, i64 x) -> void { if (i == (int)v.size()) { ret.push_back(x); return; } rc(rc, i + 1, x); for (int j = 0; j < v[i].second; j++) rc(rc, i + 1, x *= v[i].first); }; f(f, 0, 1); sort(begin(ret), end(ret)); return ret; } } // namespace fast_factorize using fast_factorize::divisors; using fast_factorize::factor_count; using fast_factorize::factorize; /** * @brief 高速素因数分解(Miller Rabin/Pollard's Rho) * @docs docs/prime/fast-factorize.md */ // constexpr ... for constexpr bool prime() template <int m> struct StaticModint { using mint = StaticModint; unsigned int _v; static constexpr int mod() { return m; } static constexpr unsigned int umod() { return m; } constexpr StaticModint() : _v(0) {} template <class T> constexpr StaticModint(T v) { long long x = (long long)(v % (long long)(umod())); if (x < 0) x += umod(); _v = (unsigned int)(x); } constexpr unsigned int val() const { return _v; } constexpr mint &operator++() { _v++; if (_v == umod()) _v = 0; return *this; } constexpr mint &operator--() { if (_v == 0) _v = umod(); _v--; return *this; } constexpr mint operator++(int) { mint result = *this; ++*this; return result; } constexpr mint operator--(int) { mint result = *this; --*this; return result; } constexpr mint &operator+=(const mint &rhs) { _v += rhs._v; if (_v >= umod()) _v -= umod(); return *this; } constexpr mint &operator-=(const mint &rhs) { _v -= rhs._v; if (_v >= umod()) _v += umod(); return *this; } constexpr mint &operator*=(const mint &rhs) { unsigned long long z = _v; z *= rhs._v; _v = (unsigned int)(z % umod()); return *this; } constexpr mint &operator/=(const mint &rhs) { return (*this *= rhs.inv()); } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint() - *this; } constexpr mint pow(long long n) const { assert(n >= 0); mint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } constexpr mint inv() const { if (prime) { assert(_v); return pow(umod() - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } } friend constexpr mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend constexpr mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend constexpr mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend constexpr mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend constexpr bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; } friend constexpr bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; } friend std::ostream &operator<<(std::ostream &os, const mint &v) { return os << v.val(); } static constexpr bool prime = []() -> bool { if (m == 1) return false; if (m == 2 || m == 7 || m == 61) return true; if (m % 2 == 0) return false; unsigned int d = m - 1; while (d % 2 == 0) d /= 2; for (unsigned int a : {2, 7, 61}) { unsigned int t = d; mint y = mint(a).pow(t); while (t != m - 1 and y != 1 and y != m - 1) { y *= y; t <<= 1; } if (y != m - 1 and t % 2 == 0) { return false; } } return true; }(); static constexpr std::pair<int, int> inv_gcd(int a, int b) { if (a == 0) return {b, 0}; int s = b, t = a, m0 = 0, m1 = 1; while (t) { const int u = s / t; s -= t * u; m0 -= m1 * u; std::swap(s, t); std::swap(m0, m1); } if (m0 < 0) m0 += b / s; return {s, m0}; } }; using mint107 = StaticModint<1000000007>; using mint998 = StaticModint<998244353>; using mint = mint998; void solve() { I64(N); auto pf = factor_count(N); const int M = 60; const int L = LEN(pf); vector calc(L, vector<i64>(M + 1)); int ind = 0; FORE(p, c, pf) { // {総和, 末尾} vector dp(M + 1, vector<i64>(M + 1)); REP(i, c + 1) dp[i][i] = 1; REP(i, M) { REP(b, M + 1) { calc[ind][i + 1] += dp[c][b]; } vector np(M + 1, vector<i64>(M + 1)); REP(s, M + 1) REP(b, M + 1) { if (dp[s][b] == 0) continue; REP(nx, b + 1) { if (nx + s <= c) np[s + nx][nx] += dp[s][b]; } } swap(dp, np); } ind++; } i64 ans = 0; REP(len, 1, M + 1) { mint c = 1; REP(i, L) c *= calc[i][len]; mint er = 1; REP(i, L) er *= calc[i][len - 1]; mint cur = c - er; ans += cur.val(); } print(ans); return; } int main() { solve(); return 0; }