結果
問題 | No.1554 array_and_me |
ユーザー |
|
提出日時 | 2021-06-19 15:08:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 685 ms / 2,000 ms |
コード長 | 747 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 113,128 KB |
最終ジャッジ日時 | 2024-06-22 22:04:56 |
合計ジャッジ時間 | 18,130 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
from heapq import *mod = 998244353fact = [1,1]finv = [1,1]inv = [0,1]for i in range(2,10**5+5):fact.append((fact[-1]*i)%mod)inv.append((inv[mod%i]*(mod-mod//i))%mod)finv.append((finv[-1]*inv[-1])%mod)def solve():n,k = map(int,input().split())A = list(map(int,input().split()))X = [0]*nh = [[-a,i] for i,a in enumerate(A)]heapify(h)for _ in range(k):v,i = heappop(h)X[i] += 1heappush(h,[-A[i]/(X[i]+1),i])ans = fact[k]for i,(x,a) in enumerate(zip(X,A)):ans *= pow(a,x,mod)*finv[x]%modans %= modbase = pow(sum(A),k,mod)ans *= pow(base,mod-2,mod)ans %= modprint(ans)t = int(input())for _ in range(t):solve()