結果
問題 |
No.1554 array_and_me
|
ユーザー |
|
提出日時 | 2025-04-17 21:57:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 2,020 bytes |
コンパイル時間 | 1,679 ms |
コンパイル使用メモリ | 200,424 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-17 21:57:46 |
合計ジャッジ時間 | 4,416 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
/* from fractions import Fraction from heapq import* MOD=998244353 T=int(input()) for _ in range(T): N,K=map(int,input().split()) A=list(map(int,input().split())) hq=[-Fraction(A[i],1) for i in range(N)] heapify(hq) ans=pow(sum(A),-K,MOD) for i in range(K): nf=heappop(hq) ans*=(i+1) ans*=-nf.numerator ans*=pow(nf.denominator,-1,MOD) ans%=MOD heappush(hq,Fraction(nf.numerator,nf.denominator+1)) print(ans) */ #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; long long modpow(long long a, long long b, long long mod) { long long res = 1; a %= mod; if (b < 0) { // Compute modular inverse of a^(-b) a = modpow(a, mod - 2, mod); b = -b; } while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } long long modinv(long long a, long long mod) { return modpow(a, mod - 2, mod); } struct Frac { long long num, den; Frac(long long n, long long d) { num = n; den = d; } bool operator<(const Frac& other) const { return num * other.den < other.num * den; } }; int main() { int T; cin >> T; while (T--) { int N, K; cin >> N >> K; vector<int> A(N); long long sumA = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; sumA += A[i]; } // Min-heap using greater<>, so store negative fractions priority_queue<Frac> hq; for (int i = 0; i < N; ++i) { hq.push(Frac(A[i], 1)); } long long ans = modpow(sumA, -K, MOD); for (int i = 0; i < K; ++i) { Frac nf = hq.top(); hq.pop(); ans = ans * (i + 1) % MOD; ans = ans * (nf.num) % MOD; ans = ans * modinv(nf.den, MOD) % MOD; hq.push(Frac(nf.num, nf.den + 1)); } cout << ans << '\n'; } return 0; }