結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-27 01:26:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 421 ms / 3,000 ms |
コード長 | 8,080 bytes |
コンパイル時間 | 2,898 ms |
コンパイル使用メモリ | 207,812 KB |
最終ジャッジ日時 | 2025-02-13 08:51:08 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#line 2 "src/cp-template.hpp"#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using uint = unsigned int;using ull = unsigned long long;using i128 = __int128_t;template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }#line 2 "src/utility/rep_itr.hpp"template < class T > struct itr {T i, d;constexpr itr(const T i) noexcept : i(i), d(1) {}constexpr itr(const T i, const T d) noexcept : i(i), d(d) {}void operator++() noexcept { i += d; }constexpr int operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept {return d > 0 ? i < x.i : i > x.i;}};template < class T > struct rep {const itr< T > s, t;constexpr rep(const T t) noexcept : s(0), t(t) {}constexpr rep(const T s, const T t) noexcept : s(s), t(t) {}constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {}constexpr auto begin() const noexcept { return s; }constexpr auto end() const noexcept { return t; }};template < class T > struct revrep {const itr < T > s, t;constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {}constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {}constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {}constexpr auto begin() const noexcept { return s; }constexpr auto end() const noexcept { return t; }};#line 2 "src/utility/io.hpp"namespace scanner {struct sca {template < class T > operator T() {T s; cin >> s; return s;}};struct vec {int n;vec(int n) : n(n) {}template < class T > operator vector< T >() {vector< T > v(n);for(T& x : v) cin >> x;return v;}};struct mat {int h,w;mat(int h, int w) : h(h), w(w) {}template < class T > operator vector< vector< T > >() {vector m(h, vector< T >(w));for(vector< T >& v : m) for(T& x : v) cin >> x;return m;}};struct speedup {speedup() {cin.tie(0);ios::sync_with_stdio(0);}} su;}scanner::sca in() { return scanner::sca(); }scanner::vec in(int n) { return scanner::vec(n); }scanner::mat in(int h, int w) { return scanner::mat(h, w); }namespace printer {void precision(int d) {cout << fixed << setprecision(d);}void flush() {cout.flush();}}int print() { cout << '\n'; return 0; }template < class head, class... tail > int print(head&& h, tail&&... t) {cout << h; if(sizeof...(tail)) cout << ' ';return print(forward<tail>(t)...);}template < class T > int print(vector< T > a, char sep = ' ') {int n = a.size();for(int i : rep(n)) cout << a[i] << (i != n - 1 ? sep : '\n');return 0;}template < class T > int print(vector< vector< T > > a) {if(a.empty()) return 0;int h = a.size(), w = a[0].size();for(int i : rep(h)) for(int j : rep(w)) cout << a[i][j] << (j != w - 1 ? ' ' : '\n');return 0;}#line 2 "src/utility/key_val.hpp"template < class K, class V >struct key_val {K key; V val;key_val() {}key_val(K key, V val) : key(key), val(val) {}};#line 2 "src/utility/vec_op.hpp"template < class T >key_val< int, T > max_of(const vector< T >& a) {int i = max_element(a.begin(), a.end()) - a.begin();return {i, a[i]};}template < class T >key_val< int, T > min_of(const vector< T >& a) {int i = min_element(a.begin(), a.end()) - a.begin();return {i, a[i]};}template < class T >T sum_of(const vector< T >& a) {T sum = 0;for(const T x : a) sum += x;return sum;}template < class T >vector<int> freq_of(const vector< T >& a, T L, T R) {vector<int> res(R - L);for(const T x : a) res[x - L]++;return res;}template < class T >vector<int> freq_of(const vector< T >& a, T R) {return freq_of(a, T(0), R);}template < class T >struct prefix_sum {vector< T > s;prefix_sum(const vector< T >& a) : s(a) {s.insert(s.begin(), T(0));for(int i : rep(a.size())) s[i + 1] += s[i];}// [L, R)T sum(int L, int R) {return s[R] - s[L];}};#line 1 "src/number/modint.hpp"struct modinfo { uint mod, root, isprime; };template < modinfo const &ref >struct modint {static constexpr uint const &mod = ref.mod;static constexpr uint const &root = ref.root;static constexpr uint const &isprime = ref.isprime;uint v = 0;constexpr modint& s(uint v) { this->v = v < mod ? v : v - mod; return *this; }constexpr modint(ll v = 0) { s(v % mod + mod); }modint operator-() const { return modint() - *this; }modint& operator+=(const modint& rhs) { return s(v + rhs.v); }modint& operator-=(const modint& rhs) { return s(v + mod - rhs.v); }modint& operator*=(const modint& rhs) { v = ull(v) * rhs.v % mod; return *this; }modint& operator/=(const modint& rhs) { return *this *= inv(rhs); }modint operator+(const modint& rhs) const { return modint(*this) += rhs; }modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }friend modint pow(modint x, ll n) { modint res(1); while(n > 0) { if(n & 1) res *= x; x *= x; n >>= 1; } return res; }friend modint inv(modint v) {if(isprime) {return pow(v, mod - 2);} else {ll a = v.v, b = modint::mod, x = 1, y = 0, t;while(b > 0) { t = a / b; swap(a -= t * b, b); swap(x -= t * y, y); }return modint(x);}}friend modint operator+(int x, const modint& y) { return modint(x) + y; }friend modint operator-(int x, const modint& y) { return modint(x) - y; }friend modint operator*(int x, const modint& y) { return modint(x) * y; }friend modint operator/(int x, const modint& y) { return modint(x) / y; }friend istream& operator>>(istream& is, modint& m) { ll x; is >> x; m = modint(x); return is; }friend ostream& operator<<(ostream& os, const modint& m) { return os << m.v; }bool operator==(const modint& r) const { return v == r.v; }bool operator!=(const modint& r) const { return v != r.v; }static uint get_mod() { return mod; }};constexpr modinfo base998244353 { 998244353, 3, 1 };constexpr modinfo base1000000007 { 1000000007, 0, 1 };using mint998244353 = modint< base998244353 >;using mint1000000007 = modint< base1000000007 >;#line 3 "A.cpp"using mint = mint998244353;int main() {ll N = in(), N2 = N;vector<ll> P, E, D;for(ll x = 1; x * x <= N; x++) {if(N2 % x == 0) {if(x != 1) {P.push_back(x);E.push_back(1);while(N2 % x == 0) N2 /= x, E.back()++;}}}if(N2 > 1) P.push_back(N2), E.push_back(1);for(ll x = 1; x * x <= N; x++) {if(N % x == 0) {D.push_back(x);if(x * x != N) D.push_back(N / x);}}sort(D.begin(), D.end());vector<vector<ll>> DE(D.size(), vector<ll>(P.size(), 0));for(int i : rep(D.size())) {for(int k : rep(P.size())) {ll x = D[i];while(x % P[k] == 0) x /= P[k], DE[i][k]++;}}vector<mint> dp(D.size(), 0);dp[0] = 1;for(int u : rep(int(D.size()))) for(int v : rep(u + 1, int(D.size()))) {if(D[v] % D[u] == 0) {mint c = 1;for(int k : rep(P.size())) {if(DE[u][k] == DE[v][k]) {c *= DE[u][k] + 1;}}dp[v] += c * dp[u];}}print(dp.back());}