結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー SSRS
提出日時 2023-05-26 22:30:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,043 ms / 3,000 ms
コード長 1,107 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 174,000 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-25 08:30:33
合計ジャッジ時間 11,077 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main(){
  long long N;
  cin >> N;
  vector<pair<long long, int>> pf;
  for (int i = 2; (long long) i * i <= N; i++){
    if (N % i == 0){
      int cnt = 0;
      while (N % i == 0){
        N /= i;
        cnt++;
      }
      pf.push_back(make_pair(i, cnt));
    }
  }
  if (N > 1){
    pf.push_back(make_pair(N, 1));
  }
  int cnt = pf.size();
  vector<int> P(cnt + 1);
  P[0] = 1;
  for (int i = 0; i < cnt; i++){
    P[i + 1] = P[i] * (pf[i].second + 1);
  }
  vector<long long> dp(P[cnt], 0);
  dp[0] = 1;
  for (int i = 1; i < P[cnt]; i++){
    for (int j = 0; j < i; j++){
      bool ok = true;
      long long mul = 1;
      for (int k = 0; k < cnt; k++){
        long long a = i % P[k + 1] / P[k];
        long long b = j % P[k + 1] / P[k];
        if (a < b){
          ok = false;
          break;
        }
        if (a == b){
          mul *= a + 1;
        }
        mul %= MOD;
      }
      if (ok){
        dp[i] += dp[j] * mul;
        dp[i] %= MOD;
      }
    }
  }
  cout << dp[P[cnt] - 1] << endl;
}
0