結果

問題 No.2318 Phys Bone Maker
ユーザー erbowlerbowl
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 technique
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x) {
return -par[root(x)];
}
};
// Segment Tree
template<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^e
return 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;
}
};
// modint
template<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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0