結果
| 問題 | No.2798 Multiple Chain |
| ユーザー |
 Misuki
|
| 提出日時 | 2024-06-28 22:15:04 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,524 bytes |
| コンパイル時間 | 2,820 ms |
| コンパイル使用メモリ | 216,936 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-28 22:15:15 |
| 合計ジャッジ時間 | 4,262 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 51 |
ソースコード
#pragma GCC optimize("O2")#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <variant>#include <bit>#include <compare>#include <concepts>#include <numbers>#include <ranges>#include <span>//#define int ll#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)#define INT128_MIN (-INT128_MAX - 1)#define clock chrono::steady_clock::now().time_since_epoch().count()#ifdef DEBUG#define dbg(x) cout << (#x) << " = " << (x) << '\n'#else#define dbg(x)#endifusing namespace std;template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP = plus<T>>void pSum(rng &&v) {if (!v.empty())for(T p = v[0]; T &x : v | views::drop(1))x = p = OP()(p, x);}template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP>void pSum(rng &&v, OP op) {if (!v.empty())for(T p = v[0]; T &x : v | views::drop(1))x = p = op(p, x);}template<class T>T floorDiv(T a, T b) {if (b < 0) a *= -1, b *= -1;return a >= 0 ? a / b : (a - b + 1) / b;}template<class T>T ceilDiv(T a, T b) {if (b < 0) a *= -1, b *= -1;return a >= 0 ? (a + b - 1) / b : a / b;}template<class T>ostream& operator<<(ostream& os, const pair<T, T> pr) {return os << pr.first << ' ' << pr.second;}template<class T, size_t N>ostream& operator<<(ostream& os, const array<T, N> &arr) {for(const T &X : arr)os << X << ' ';return os;}template<class T>ostream& operator<<(ostream& os, const vector<T> &vec) {for(const T &X : vec)os << X << ' ';return os;}template<class T>ostream& operator<<(ostream& os, const set<T> &s) {for(const T &x : s)os << x << ' ';return os;}#define rep(i, a, b) for (int i = int(a); i < int(b); i++)#define trav(a, x) for (auto& a : x)#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)#define all(x) x.begin(), x.end()template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }template <class T> using vc = vector<T>;template <class T> using vvc = vc<vc<T>>;using ll = int64_t;using vi = vc<int>;using pii = pair<int, int>;using uint = uint32_t;using ull = uint64_t;mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());template <class F>struct ycr {F f;template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}template <class... Args> decltype(auto) operator()(Args&&... args) {return f(ref(*this), forward<Args>(args)...);}};template <class F> decltype(auto) yc(F&& f) {return ycr<decay_t<F>>(forward<F>(f));}// Reference: https://judge.yosupo.jp/submission/110118struct montgomery {using T = ull;using u128 = __uint128_t;T n, n2, r, t, e;montgomery(T n_) : n(n_) {assert(n < (T(1) << 62));assert(n % 2 == 1);n2 = n * 2;r = n & 3;rep(_,0,5) r *= 2-n*r;r = -r;assert(r * n == T(-1));t = -T(n) % n;e = T(-u128(n) % n);}T reduce(u128 a) const {return T((a + u128(T(a) * r) * n) >> 64);}T mult(T a, T b) const {return reduce(u128(a) * b);}T encode(T a) const {return mult(a, e);}T decode(T a) const {a = reduce(a);return a < n ? a : a-n;}T pow(T a, ll b) const {assert(b >= 0);T v = t;while (b) {if (b & 1) v = mult(v, a);a = mult(a, a);b >>= 1;}return v;}bool is_prime() const {assert(n >= 3);assert(n & 1);T d = n-1;int s = __builtin_ctzll(d);d >>= s;auto check = [&](T a) -> int {a %= n;if (a == 0) return 1;T p = pow(encode(a), d);if (decode(p) == 1 || decode(p) == n-1) return 0;for (int z = 0; z < s; z++) {p = mult(p, p);if (decode(p) == n-1) return 0;}return -1;};for (T a : {2,325,9375,28178,450775,9780504,1795265022}) {int w = check(a);if (w) return w == 1;}return true;}ull pollard() const {assert(n >= 3);assert(n & 1);if (is_prime()) return n;while (true) {T c = mt() % (n-1) + 1;T y = mt() % (n-1) + 1;auto f = [&](T a) -> T {return reduce(u128(a) * a + c);};for (T s = 1; ; s *= 2) {T x = n2-y;T m = min(T(1) << (__lg(n)/6), s);rep(i,0,s/m) {T w = t, z = y;rep(j,0,m) {y = f(y);w = mult(w, y+x);}T g = __gcd(decode(w), n);if (g != 1) {if (g < n) return g;rep(j,0,m) {z = f(z);if ((g = __gcd(decode(z+x), n)) != 1) {if (g < n) return g;goto fail;}}assert(false);}}}fail:;}}};using ull = uint64_t;bool is_prime(ull n) {if (n <= 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;return montgomery(n).is_prime();}ull get_divisor(ull n) {assert(n > 1);if (n % 2 == 0) return 2;return montgomery(n).pollard();}vc<ull> factorize(ull n) {vc<ull> res;yc([&](auto self, ull v) -> void {if (v == 1) return;ull d = get_divisor(v);if (d == v) {res.push_back(d);return;}self(d);self(v/d);})(n);return res;}signed main() {ios::sync_with_stdio(false), cin.tie(NULL);ull n; cin >> n;map<int, int> m;for(auto x : factorize(n)) m[x]++;int mxL = 0;for(auto [_, f] : m) mxL = max(mxL, f);int ans = 0;for(int l = 1; l <= mxL; l++) {array<int, 2> cnt = {1, 0};for(auto [_, f] : m) {vector dp(l + 1, vector(2, vector<int>(f + 1)));dp[0][0][f] = cnt[0], dp[0][1][f] = cnt[1];for(int i = 0; i < l; i++) for(int j : {0, 1}) for(int k = 0; k <= f; k++) {for(int r = 0; k - r * (i + 1) >= 0; r++)dp[i + 1][j | (r != 0 and i + 1 == l)][k - r * (i + 1)] += dp[i][j][k];}cnt[0] = dp[l][0][0], cnt[1] = dp[l][1][0];}ans += cnt[1];}cout << ans << '\n';return 0;}