結果
問題 |
No.766 金魚すくい
|
ユーザー |
|
提出日時 | 2023-07-13 01:01:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 1,500 ms |
コード長 | 849 bytes |
コンパイル時間 | 3,974 ms |
コンパイル使用メモリ | 234,500 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 13:39:41 |
合計ジャッジ時間 | 6,042 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using mint = atcoder::modint1000000007; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, p; cin >> n >> m >> p; vector<int> a(n); for(auto &&v : a) cin >> v; vector<mint> fact(n + m), inv(n + m); fact[0] = 1; for(int i = 1; i < n + m; i++) fact[i] = i * fact[i - 1]; inv.back() = 1 / fact.back(); for(int i = inv.size() - 1; i >= 1; i--) inv[i - 1] = i * inv[i]; mint ans, s, rem, P = mint(100 - p) / 100, coef = (1 - P).pow(m--); sort(a.rbegin(), a.rend()); for(int i = 0; i < n; i++){ mint tmp = fact[m + i] * inv[i] * coef; ans += tmp * s; rem += tmp; coef *= P; s += a[i]; } ans *= inv[m]; ans += (1 - rem * inv[m]) * s; cout << ans.val() << '\n'; }