結果

問題 No.2963 Mecha DESU
ユーザー srjywrdnprkt
提出日時 2024-11-18 12:26:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 119 ms / 2,000 ms
コード長 882 bytes
コンパイル時間 2,134 ms
コンパイル使用メモリ 197,112 KB
最終ジャッジ日時 2025-02-25 05:25:55
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       p(i)=ゾンビiが1回以上感電する確率
       K回ともiの約数以外のCが選ばれる事象の余事象
       1-(1-(iの約数であるものの数)/M)^K
    */
    int N, M, K, L=1000000, A;
    cin >> N >> M >> K;
    vector<int> cnt(L+1);
    for (int i=1; i<=M; i++){
        cin >> A;
        cnt[A]++;
    }
    vector<int> cnt2(L+1);
    for (int i=1; i<=L; i++){
        for (int j=i; j<=L; j+=i){
            cnt2[j] += cnt[i];
        }
    }
    mint ans=0, iv=mint(M).inv();
    for (int i=1; i<=N; i++){
        ans += mint(1) - mint(mint(1)-iv*cnt2[i]).pow(K);
    }
    cout << ans.val() << endl;

    return 0;
}
0