結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-26 21:41:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 3,000 ms |
コード長 | 909 bytes |
コンパイル時間 | 1,117 ms |
コンパイル使用メモリ | 91,444 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 05:48:32 |
合計ジャッジ時間 | 2,876 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<iostream> #include<vector> #include<map> #include<algorithm> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; map<vector<int>,mint>memo; mint solve(vector<int>); mint dfs(int id,vector<int>&F,int flag) { if(id==F.size()) { if(flag)return solve(F); else return mint::raw(0); } int c=F[id]; mint ret=mint::raw(c+1)*dfs(id+1,F,flag); while(F[id]>0) { F[id]--; ret+=dfs(id+1,F,1); } F[id]=c; return ret; } mint solve(vector<int>F) { sort(F.begin(),F.end()); reverse(F.begin(),F.end()); while(!F.empty()&&F.back()==0)F.pop_back(); if(F.empty())return mint::raw(1); if(memo.find(F)!=memo.end())return memo[F]; mint ans=dfs(0,F,0); return memo[F]=ans; } int main() { long N; cin>>N; vector<int>F; for(long i=2;i*i<=N;i++)if(N%i==0) { F.push_back(0); while(N%i==0)N/=i,F.back()++; } if(N>=2)F.push_back(1); cout<<solve(F).val()<<endl; }