結果

問題 No.3187 Mingle
コンテスト
ユーザー 蜜蜂
提出日時 2025-06-02 18:54:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 928 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 95,836 KB
実行使用メモリ 418,176 KB
最終ジャッジ日時 2025-06-13 14:37:28
合計ジャッジ時間 45,891 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

#include <atcoder/modint>
using namespace atcoder;

using mint = modint998244353;

int main(){
  int n;
  cin >> n;

  int m = 350;
  vector<int> d(n + 1, 0);
  vector<mint> f(n + 1, 0);
  vector<vector<mint>> f_sum(m + 1, vector<mint>(n + 1, 0));

  for(int i = 1; i <= n; i++){
    for(int j = i; j <= n; j += i){
      d[j]++;
    }
  }

  for(int i = 3; i <= n; i++){
    mint sum = 0;

    for(int j = 1; j <= m; j++){
      if(i % j != 0) sum += f[i - i % j];
    }
    for(int j = 1; j <= m; j++){
      int l = i / (j + 1) + 1;
      int r = i / j;
      if(r * j == i) r--;
      l = max(l, m + 1);
      if(l > r) break;
      sum += f_sum[j][r * j] - f_sum[j][(l - 1) * j];
    }
    f[i] = (sum / i + 1) * i / (i - d[i]);
    for(int j = 1; j <= m; j++){
      if(i % j == 0) f_sum[j][i] = f_sum[j][i - j] + f[i];
    }
  }

  cout << f[n].val() << endl;
}
0