結果
問題 | No.2963 Mecha DESU |
ユーザー |
|
提出日時 | 2024-10-21 22:38:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 501 bytes |
コンパイル時間 | 3,327 ms |
コンパイル使用メモリ | 81,908 KB |
実行使用メモリ | 108,228 KB |
最終ジャッジ日時 | 2024-10-26 11:01:21 |
合計ジャッジ時間 | 9,160 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
from collections import defaultdict MOD=998244353 N,M,K=list(map(int,input().split())) A=list(map(int,input().split())) card=[0]*(N+1) for i in A: if i<=N: card[i]+=1 cnt=[0]*(N+1) for i in range(1,N+1): if card[i]==0: continue for j in range(i,N+1,i): cnt[j]+=card[i] ans=defaultdict(int) for i in range(1,N+1): ans[M-cnt[i]]+=1 ANS=(N*pow(M,K,MOD))%MOD for i in range(1,M+1): ANS=(ANS-ans[i]*pow(i,K,MOD))%MOD #print(ANS) #print(ans) ANS=(ANS*pow(pow(M,K,MOD),MOD-2,MOD))%MOD print(ANS)