結果
問題 |
No.829 成長関数インフレ中
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:00:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,946 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 82,676 KB |
実行使用メモリ | 134,516 KB |
最終ジャッジ日時 | 2025-04-09 21:01:28 |
合計ジャッジ時間 | 3,045 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 2 |
ソースコード
MOD = 10**9 + 7 def main(): import sys from itertools import groupby input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr +=1 B_val = int(input[ptr]) ptr +=1 S = list(map(int, input[ptr:ptr+N])) ptr +=N # Sort S in non-increasing order S.sort(reverse=True) # Group by value and get counts groups = [] current_val = None current_count = 0 for val in S: if val != current_val: if current_val is not None: groups.append((current_val, current_count)) current_val = val current_count = 1 else: current_count +=1 if current_count >0: groups.append((current_val, current_count)) # Compute m_x (prefix sum of previous group counts) m_x_list = [] prefix =0 for val, count in groups: m_x_list.append(prefix) prefix += count # Compute N! mod MOD factorial = [1] * (N+1) for i in range(1, N+1): factorial[i] = factorial[i-1] * i % MOD fact_n = factorial[N] B = B_val % MOD product_num = 1 product_den = 1 sum_terms =0 for (val, count), m_x in zip(groups, m_x_list): a_x = count b_x = m_x B_c_m = (a_x * B + b_x) % MOD denom = (a_x + b_x) % MOD product_num = product_num * B_c_m % MOD product_den = product_den * denom % MOD denominator_x = B_c_m inv_denominator = pow(denominator_x, MOD-2, MOD) term_sum = a_x * inv_denominator % MOD sum_terms = (sum_terms + term_sum) % MOD inv_product_den = pow(product_den, MOD-2, MOD) product_terms = product_num * inv_product_den % MOD result = fact_n * B % MOD result = result * product_terms % MOD result = result * sum_terms % MOD print(result) if __name__ == "__main__": main()