結果

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

ソースコード

diff # 

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