結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-27 10:56:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,311 ms / 3,000 ms |
コード長 | 8,214 bytes |
コンパイル時間 | 1,985 ms |
コンパイル使用メモリ | 206,508 KB |
最終ジャッジ日時 | 2025-02-13 09:02:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;#define int long long// こっちを使おう!// __builtin_popcountll// 1<<n -> オーバーフローstruct UnionFind {vector<int> par;UnionFind() { }UnionFind(int n) : par(n, -1) { }void init(int n) { par.assign(n, -1); }int root(int x) {if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x, y); // merge techniquepar[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};// Segment Treetemplate<class Monoid> struct SegTree {using Func = function<Monoid(Monoid, Monoid)>;int N;Func F;Monoid IDENTITY;int SIZE_R;vector<Monoid> dat;/* initialization */SegTree() {}SegTree(int n, const Func f, const Monoid &identity): N(n), F(f), IDENTITY(identity) {SIZE_R = 1;while (SIZE_R < n) SIZE_R *= 2;dat.assign(SIZE_R * 2, IDENTITY);}void init(int n, const Func f, const Monoid &identity) {N = n;F = f;IDENTITY = identity;SIZE_R = 1;while (SIZE_R < n) SIZE_R *= 2;dat.assign(SIZE_R * 2, IDENTITY);}/* set, a is 0-indexed *//* build(): O(N) */void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }void build() {for (int k = SIZE_R - 1; k > 0; --k)dat[k] = F(dat[k*2], dat[k*2+1]);}/* update a, a is 0-indexed, O(log N) */void update(int a, const Monoid &v) {int k = a + SIZE_R;dat[k] = v;while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);}/* get [a, b), a and b are 0-indexed, O(log N) */Monoid get(int a, int b) {Monoid vleft = IDENTITY, vright = IDENTITY;for (int left = a + SIZE_R, right = b + SIZE_R; left < right;left >>= 1, right >>= 1) {if (left & 1) vleft = F(vleft, dat[left++]);if (right & 1) vright = F(dat[--right], vright);}return F(vleft, vright);}Monoid all_get() { return dat[1]; }Monoid operator [] (int a) { return dat[a + SIZE_R]; }/* get max r that f(get(l, r)) = True (0-indexed), O(log N) *//* f(IDENTITY) need to be True */int max_right(const function<bool(Monoid)> f, int l = 0) {if (l == N) return N;l += SIZE_R;Monoid sum = IDENTITY;do {while (l % 2 == 0) l >>= 1;if (!f(F(sum, dat[l]))) {while (l < SIZE_R) {l = l * 2;if (f(F(sum, dat[l]))) {sum = F(sum, dat[l]);++l;}}return l - SIZE_R;}sum = F(sum, dat[l]);++l;} while ((l & -l) != l); // stop if l = 2^ereturn N;}/* get min l that f(get(l, r)) = True (0-indexed), O(log N) *//* f(IDENTITY) need to be True */int min_left(const function<bool(Monoid)> f, int r = -1) {if (r == 0) return 0;if (r == -1) r = N;r += SIZE_R;Monoid sum = IDENTITY;do {--r;while (r > 1 && (r % 2)) r >>= 1;if (!f(F(dat[r], sum))) {while (r < SIZE_R) {r = r * 2 + 1;if (f(F(dat[r], sum))) {sum = F(dat[r], sum);--r;}}return r + 1 - SIZE_R;}sum = F(dat[r], sum);} while ((r & -r) != r);return 0;}/* debug */void print() {for (int i = 0; i < N; ++i) {cout << (*this)[i];if (i != N-1) cout << ",";}cout << endl;}};// modinttemplate<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {if (n == 0) return 1;if (n < 0) return modpow(modinv(r), -n);auto t = modpow(r, n / 2);t = t * t;if (n & 1) t = t * r;return t;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}};vector<long long> calc_divisor(long long n) {vector<long long> res;for (long long i = 1LL; i*i <= n; ++i) {if (n % i == 0) {res.push_back(i);long long j = n / i;if (j != i) res.push_back(j);}}sort(res.begin(), res.end());return res;}// const int MOD = 1000000007;const int MOD = 998244353;using mint = Fp<MOD>;signed main(){ll n;std::cin >> n;auto div = calc_divisor(n);vector<mint> dp(div.size());dp[0] = 1;set<ll> primes;for (int i = 1; i < div.size(); i++) {bool yes = true;for (int j = 1; j < i; j++) {if(div[i]%div[j]==0){yes=false;break;}}if(yes)primes.insert(div[i]);}for (int i = 1; i < div.size(); i++) {for (int j = 0; j < i; j++) {if(div[i]%div[j]==0){ll cnt = 1;ll av = div[j];ll bv = div[i];for (auto e : primes) {ll a,b;a = b = 0;while(av%e==0){av/=e;a++;}while(bv%e==0){bv/=e;b++;}if(a==b){cnt *= a+1;}}dp[i] += dp[j]*cnt;}}// std::cout << dp[i] << std::endl;}std::cout << dp.back() << std::endl;}