結果
問題 | No.766 金魚すくい |
ユーザー |
![]() |
提出日時 | 2023-08-17 10:15:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 1,500 ms |
コード長 | 1,822 bytes |
コンパイル時間 | 968 ms |
コンパイル使用メモリ | 79,276 KB |
実行使用メモリ | 20,112 KB |
最終ジャッジ日時 | 2024-11-26 06:12:55 |
合計ジャッジ時間 | 4,972 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;using ll = long long;constexpr ll MOD = 1'000'000'007;struct Combination{using ll = long long;const int n;// const int MOD = 998244353;vector<ll> fac, ifac;ll mp(ll a, ll x) const {ll res = 1;for(; x > 0; x >>= 1){if(x&1){res *= a; res %= MOD;}a *= a; a %= MOD;}return res;}Combination(int _n = 1000000): n(_n), fac(vector<ll>(_n+1)), ifac(vector<ll>(_n+1)){fac[0] = 1;for(int i = 1; i <= n; i++) fac[i] = (fac[i-1]*i)%MOD;ifac[n] = mp(fac[n], MOD-2);for(int i = n; i > 0; i--) ifac[i-1] = (ifac[i]*i)%MOD;}ll operator()(int n, int k) const {if (k < 0 || k > n) return 0;return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}};ll modpow(ll a, ll x){ll res = 1;a %= MOD;for(; x > 0; x >>= 1){if(x & 1){res *= a;res %= MOD;}a *= a;a %= MOD;}return res;}ll inv(ll a){return modpow(a, MOD-2);}int main(){int n, m, p; cin >> n >> m >> p;vector<int> v(n);for(auto &it: v) cin >> it;sort(v.begin(), v.end(), greater<int>());vector<ll> vtot(n+1, 0);for(int i = 0; i < n; i++) vtot[i+1] = (vtot[i]+v[i])%MOD;Combination comb{};ll ans = 0;const ll q = inv(100)*p%MOD;const ll r = inv(100)*(100-p)%MOD;for(int i = 0; i < n; i++){ans += modpow(q, m)*modpow(r, i)%MOD*comb(m+i-1, i)%MOD*vtot[i]%MOD;ans %= MOD;}for(int i = 0; i < m; i++){ans += modpow(r, n)*modpow(q, i)%MOD*comb(n+i-1, i)%MOD*vtot[n]%MOD;ans %= MOD;}cout << ans << endl;return 0;}