結果
問題 |
No.766 金魚すくい
|
ユーザー |
|
提出日時 | 2025-08-24 01:45:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 257 ms / 1,500 ms |
コード長 | 2,477 bytes |
コンパイル時間 | 435 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 95,240 KB |
最終ジャッジ日時 | 2025-08-24 01:45:22 |
合計ジャッジ時間 | 7,773 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
## https://yukicoder.me/problems/no/423 MAX_VALUE = 1_000_000_000_000_000_000 MIN_VALUE = -1_000_000_000_000_000_000 MOD = 1_000_000_007 def _sanity(): assert 10**17 <= MAX_VALUE <= 10**19, f"MAX_VALUE suspicious: {MAX_VALUE}" assert -10**19 <= MIN_VALUE <= -10**17, f"MIN_VALUE suspicious: {MIN_VALUE}" assert MOD in (998_244_353, 1_000_000_007) _sanity() class CombinationCalculator: """ modを考慮したPermutation, Combinationを計算するためのクラス """ def __init__(self, size, mod): self.mod = mod self.factorial = [0] * (size + 1) self.factorial[0] = 1 for i in range(1, size + 1): self.factorial[i] = (i * self.factorial[i - 1]) % self.mod self.inv_factorial = [0] * (size + 1) self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod) for i in reversed(range(size)): self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod def calc_combination(self, n, r): if n < 0 or n < r or r < 0: return 0 if r == 0 or n == r: return 1 ans = self.inv_factorial[n - r] * self.inv_factorial[r] ans %= self.mod ans *= self.factorial[n] ans %= self.mod return ans def calc_permutation(self, n, r): if n < 0 or n < r: return 0 ans = self.inv_factorial[n - r] ans *= self.factorial[n] ans %= self.mod return ans def main(): N, M, P = map(int, input().split()) V = list(map(int, input().split())) V.sort(reverse=True) combi = CombinationCalculator(N + M, MOD) q = (P * pow(100, MOD - 2, MOD)) % MOD p = (1 - q) % MOD answer = 0 total_v = 0 # すべてのMを消費するパターン for n in range(N): x = combi.calc_combination(n + M - 1, M - 1) x *= pow(p, n, MOD) x %= MOD x *= pow(q, M, MOD) x %= MOD answer += (total_v * x) % MOD answer %= MOD total_v += V[n] total_v %= MOD # すべての金魚を掬い上げるパターン for m in range(M): x = combi.calc_combination(N - 1 + m, m) x *= pow(p, N, MOD) x %= MOD x *= pow(q, m, MOD) x %= MOD answer += (total_v * x) % MOD answer %= MOD print(answer) if __name__ == "__main__": main()