結果

問題 No.829 成長関数インフレ中
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:00:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,946 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0