結果
問題 | No.2902 ZERO!! |
ユーザー |
![]() |
提出日時 | 2024-09-27 20:16:03 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 646 ms / 2,000 ms |
コード長 | 1,278 bytes |
コンパイル時間 | 4,878 ms |
コンパイル使用メモリ | 268,952 KB |
実行使用メモリ | 99,008 KB |
最終ジャッジ日時 | 2024-09-27 20:16:37 |
合計ジャッジ時間 | 31,814 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001LLint main(){vector<long long> p;vector<vector<long long>> ps(1000001,vector<long long>());for(long long i=1;i<=1000000;i++){if(i==1)continue;if(ps[i].size()!=0)continue;p.push_back(i);for(long long j=i;j<=1000000;j+=i){ps[j].push_back(i);}}reverse(p.begin(),p.end());long long n;cin>>n;vector<mint> dp;rep(i,p.size()){long long cnt = 0;{long long t = n;while(t!=0){cnt += t/p[i];t /= p[i];}}vector<mint> ndp(cnt+1);while(dp.size()<ndp.size())dp.push_back(0);ndp = dp;{mint sum = 0;int cr = cnt+1;vector<long long> cs(cnt+1);for(long long j=1;j<=cnt;j++){long long nv = cnt/j;while(cr > nv){cr --;sum += dp[cr];}ndp[nv] += sum;cs[nv]++;ndp[nv]++;}for(int j=cnt;j>=1;j--){cs[j-1] += cs[j];}for(int j=1;j<cnt;j++){ndp[j] += dp[j] * cs[j+1];}}swap(dp,ndp);}mint ans = 0;rep(i,dp.size()){ans += dp[i] * i;}cout<<ans.val()<<endl;return 0;}