結果
問題 | No.766 金魚すくい |
ユーザー |
|
提出日時 | 2019-05-10 02:50:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 1,500 ms |
コード長 | 1,957 bytes |
コンパイル時間 | 1,830 ms |
コンパイル使用メモリ | 173,260 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2024-07-02 00:54:35 |
合計ジャッジ時間 | 3,958 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr long long mod = 1e9+7;long long pow_mod(long long b, long long p, long long mod = 1'000'000'007){long long ret = 1;while (p){if (p & 1) ret = (ret * b) % mod;b = (b * b) % mod;p >>= 1;}return ret;}class ModuloMath{private:long long N;long long mod;public:vector<long long> fac;vector<long long> invfac;ModuloMath(long long N, long long mod = 1'000'000'007): N{N}, mod{mod}, fac(N + 1, 1), invfac(N + 1, 1){for (long long i = 1; i <= N; ++i) fac[i] = (fac[i - 1] * i) % mod;invfac[N] = pow_mod(fac[N], mod - 2, mod);for (long long i = N; i != 1; --i) invfac[i - 1] = (invfac[i] * i) % mod;}long long nCr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod * invfac[r] % mod);}long long nPr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod);}long long nHr(long long n, long long r){return nCr(n + r - 1, r);}};int main(){cin.tie(0);ios::sync_with_stdio(false);long long N, M, P;cin >> N >> M >> P;vector<long long> Vs(N, 0);for (auto & v : Vs) cin >> v;sort(Vs.begin(), Vs.end());vector<long long> cum(N, 0);long long c = 0;for (int i = 0; i < N; ++i){(c += Vs[N - i - 1]) %= mod;cum[i] = c;}ModuloMath mm(N + M);long long Q = 100 - P;long long inv100 = pow_mod(100, mod-2);long long q = Q * inv100 % mod;long long p = pow_mod(P, M) * pow_mod(inv100, M) % mod;long long cump = p;long long ans = 0;for (int i = 1; i < N; ++i){(p *= q) %= mod;long long tmp = p * mm.nCr(M + i - 1, i) % mod;(cump += tmp) %= mod;(ans += cum[i - 1] * tmp % mod) %= mod;}(ans += cum[N - 1] * (1 + mod - cump) % mod) %= mod;cout << ans << endl;return 0;}