結果
問題 | No.2963 Mecha DESU |
ユーザー |
|
提出日時 | 2024-11-16 17:13:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 789 ms / 2,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 5,305 ms |
コンパイル使用メモリ | 309,008 KB |
実行使用メモリ | 129,152 KB |
最終ジャッジ日時 | 2024-11-16 17:14:35 |
合計ジャッジ時間 | 43,201 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using mint=atcoder::modint998244353;#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define int long longtemplate<long long mod,long long MAX_N>struct factional_prime{long long inv_[MAX_N+1];long long fac_[MAX_N+1];long long fac_inv_[MAX_N+1];factional_prime(){inv_[0]=0;inv_[1]=fac_[0]=fac_[1]=fac_inv_[0]=fac_inv_[1]=1;for(long long i=2;i<=MAX_N;i++){inv_[i]=((mod-mod/i)*inv_[mod%i])%mod;fac_[i]=(fac_[i-1]*i)%mod;fac_inv_[i]=(fac_inv_[i-1]*inv_[i])%mod;}}long long inv(long long n){if(n<0)return 0;return inv_[n];}long long fac(long long n){if(n<0)return 0;return fac_[n];}long long finv(long long n){if(n<0)return 0;return fac_inv_[n];}long long nCr(long long n,long long r){if(n<r||n<0||r<0)return 0;return ((fac_[n]*fac_inv_[n-r])%mod*fac_inv_[r])%mod;}long long nPr(long long n,long long r){if(n<r||n<0||r<0)return 0;return (fac_[n]*fac_inv_[n-r])%mod;}};factional_prime<998244353,5000000> fp;signed main(){int N,M,K;cin>>N>>M>>K;vector<int> A(M);for(auto&&e:A)cin>>e;vector<int> cnt(N+1);for(auto&&e:A){if(e<=N){cnt[e]++;}}for(int i=N;i>=1;i--){for(int j=2*i;j<=N;j+=i){cnt[j]+=cnt[i];}}mint ans=0;for(int i=1;i<=N;i++){ans+=1-mint(M-cnt[i]).pow(K)/mint(M).pow(K);}cout<<ans.val()<<endl;}