結果
問題 | No.766 金魚すくい |
ユーザー |
|
提出日時 | 2020-10-22 19:04:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 1,500 ms |
コード長 | 1,316 bytes |
コンパイル時間 | 2,221 ms |
コンパイル使用メモリ | 202,500 KB |
最終ジャッジ日時 | 2025-01-15 12:28:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)#define ALL(x) (x).begin(), (x).end()const double PI = acos(-1);const long long MOD = 1e9 + 7;long long modpow(long long x, long long p, long long mod) {long long ret = 1;while (p) {if (p & 1)ret = ret * x % mod;x = x * x % mod;p >>= 1;}return ret;}long long f[200000];long long g[200000];long long homo(long long n, long long r) {long long x = n + r - 1;long long y = r;return f[x] * g[y] % MOD * g[x-y] % MOD;}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n, m;long long p; // successlong long q; // failurecin >> n >> m >> q;q = q * modpow(100, MOD-2, MOD) % MOD;p = (1 - q + MOD) % MOD;vector<long long> v(n);REP (i, n) cin >> v[i];sort(v.rbegin(), v.rend());f[0] = g[0] = 1;for (int i = 1; i < 200000; i++) {f[i] = i * f[i-1] % MOD;g[i] = modpow(f[i], MOD-2, MOD);}long long ret = 0;long long acc = 1;REP (i, n) {long long tmp = homo(m, i) * modpow(p, i, MOD) % MOD * modpow(q, m, MOD) % MOD;acc = (acc - tmp + MOD) % MOD;ret += v[i] * acc % MOD;ret %= MOD;}cout << ret << endl;return 0;}