結果
問題 |
No.829 成長関数インフレ中
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:53:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,670 bytes |
コンパイル時間 | 521 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 138,740 KB |
最終ジャッジ日時 | 2025-06-12 14:55:58 |
合計ジャッジ時間 | 3,976 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 2 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 B = int(input[ptr]) ptr += 1 S = list(map(int, input[ptr:ptr+N])) ptr += N from collections import defaultdict freq = defaultdict(int) for num in S: freq[num] += 1 sorted_values = sorted(freq.keys()) m = len(sorted_values) c = [freq[v] for v in sorted_values] # Compute H_i for each group H = [0] * m for i in range(m-2, -1, -1): H[i] = H[i+1] + c[i+1] # Compute p_i for each group p = [] for i in range(m): denominator = c[i] + H[i] if denominator == 0: pi = 0 else: inv_denominator = pow(denominator, MOD-2, MOD) pi = c[i] * inv_denominator % MOD p.append(pi) # Compute P = product of (1 + p_i*(B-1)) for groups processed in reverse order P = 1 for i in reversed(range(m)): term = (1 + (B-1) * p[i]) % MOD P = P * term % MOD # Compute S_sum = sum of (p_i / (1 + p_i*(B-1))) S_sum = 0 for i in range(m): denom = (1 + (B-1) * p[i]) % MOD if denom == 0: inv_denom = 0 else: inv_denom = pow(denom, MOD-2, MOD) contribution = p[i] * inv_denom % MOD S_sum = (S_sum + contribution) % MOD # Compute E = B * P * S_sum E = B * P % MOD E = E * S_sum % MOD # Compute T = N! mod MOD fact = 1 for i in range(1, N+1): fact = fact * i % MOD # The answer is (E * T) mod MOD answer = E * fact % MOD print(answer) if __name__ == "__main__": main()