結果

問題 No.829 成長関数インフレ中
ユーザー lam6er
提出日時 2025-03-26 15:59:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,749 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 135,420 KB
最終ジャッジ日時 2025-03-26 16:00:23
合計ジャッジ時間 4,089 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    from collections import defaultdict

    N, B = map(int, sys.stdin.readline().split())
    S = list(map(int, sys.stdin.readline().split()))
    
    # Count frequency of each value
    freq = defaultdict(int)
    for s in S:
        freq[s] += 1
    
    # Sort the unique values in descending order and create groups
    sorted_values = sorted(freq.keys(), reverse=True)
    groups = []
    for v in sorted_values:
        groups.append((v, freq[v]))
    M = len(groups)
    
    # Precompute factorial mod MOD
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # Precompute k for each group (sum of m_j for groups before i)
    k_list = []
    total = 0
    for i in range(M):
        k_list.append(total)
        total += groups[i][1]
    
    # Compute p_i and term_i for each group
    p = []
    term = []
    for i in range(M):
        v, m = groups[i]
        k = k_list[i]
        denom = k + m
        inv_denom = pow(denom, MOD-2, MOD)
        pi = m * inv_denom % MOD
        p.append(pi)
        term_i = (1 - pi + pi * B) % MOD
        term.append(term_i)
    
    # Compute T = product of term_i
    T = 1
    for t in term:
        T = T * t % MOD
    
    # Compute sum_contrib = sum(p_i * T * inv(term_i) for each i)
    sum_contrib = 0
    for i in range(M):
        ti = term[i]
        inv_ti = pow(ti, MOD-2, MOD)
        contrib = p[i] * T % MOD
        contrib = contrib * inv_ti % MOD
        sum_contrib = (sum_contrib + contrib) % MOD
    
    # Calculate the final score
    B_mod = B % MOD
    score = (B_mod * sum_contrib) % MOD
    score = (score * fact[N]) % MOD
    print(score)

if __name__ == "__main__":
    main()
0