結果

問題 No.829 成長関数インフレ中
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:00:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,921 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 81,732 KB
実行使用メモリ 142,380 KB
最終ジャッジ日時 2025-06-12 20:03:53
合計ジャッジ時間 3,592 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 10**9 + 7

def main():
    N, B = map(int, sys.stdin.readline().split())
    S = list(map(int, sys.stdin.readline().split()))
    
    # Precompute factorials up to N
    fact = [1] * (N + 1)
    for i in range(1, N+1):
        fact[i] = fact[i-1] * i % MOD
    
    # Frequency count
    freq = defaultdict(int)
    for s in S:
        freq[s] += 1
    
    # Sort the unique elements
    sorted_values = sorted(freq.keys())
    groups = [(v, freq[v]) for v in sorted_values]
    k = len(groups)
    
    # Compute g_i for each group
    total_group = 0
    g = []
    for i in reversed(range(k)):
        v, m = groups[i]
        g_i = total_group
        g.append(g_i)
        total_group += m
    g = g[::-1]  # Reverse back to original order
    
    # Compute p_i for each group
    p = []
    for i in range(k):
        v, m = groups[i]
        denom = (g[i] + m) % MOD
        if denom == 0:
            p_i = 0
        else:
            inv_denom = pow(denom, MOD-2, MOD)
            p_i = m * inv_denom % MOD
        p.append(p_i)
    
    # Compute denom_i and inv_denom_i for each group
    denom = []
    inv_denom = []
    for i in range(k):
        pi = p[i]
        temp = (B - 1) % MOD
        temp = temp * pi % MOD
        denom_i = (1 + temp) % MOD
        inv_denom_i = pow(denom_i, MOD-2, MOD)
        denom.append(denom_i)
        inv_denom.append(inv_denom_i)
    
    # Compute G(B) as product of denom_i
    G_B = 1
    for di in denom:
        G_B = G_B * di % MOD
    
    # Compute G'(B)
    G_prime_B = 0
    for i in range(k):
        pi = p[i]
        term = pi * G_B % MOD
        term = term * inv_denom[i] % MOD
        G_prime_B = (G_prime_B + term) % MOD
    
    # Compute total
    total = B % MOD
    total = total * G_prime_B % MOD
    total = total * fact[N] % MOD
    
    print(total)

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