結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-27 23:27:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 549 ms / 3,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 1,135 ms |
コンパイル使用メモリ | 99,732 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 05:40:35 |
合計ジャッジ時間 | 6,399 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <iostream>#include <vector>using namespace std;#include <atcoder/modint>using mint = atcoder::modint998244353;int main() {long long N;cin >> N;vector<int> fac;for (long long p = 2; p * p <= N; ++p) {if (N % p != 0) continue;int cnt = 0;while (N % p == 0) {N /= p;++cnt;}fac.push_back(cnt);}if (N != 1) fac.push_back(1);vector<vector<int>> states;vector<int> tmp(fac.size());auto rec = [&](auto &&self, int d) -> void {if (d == int(tmp.size())) {states.push_back(tmp);return;}for (int a = 0; a <= fac.at(d); ++a) tmp.at(d) = a, self(self, d + 1);};rec(rec, 0);vector<mint> dp(states.size());dp.front() = 1;for (int i = 0; i < int(dp.size()); ++i) {for (int j = 0; j < i; ++j) {mint tmp = dp.at(j);for (int d = 0; d < int(fac.size()); ++d) {if (states.at(i).at(d) < states.at(j).at(d)) {tmp = 0;break;} else if (states.at(i).at(d) == states.at(j).at(d)) {tmp *= states.at(i).at(d) + 1;}}dp.at(i) += tmp;}}cout << dp.back().val() << endl;}