結果

問題 No.574 正多面体サイコロ
ユーザー lam6er
提出日時 2025-03-31 17:23:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 3,561 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 72,616 KB
最終ジャッジ日時 2025-03-31 17:24:10
合計ジャッジ時間 2,286 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    F, N, K = map(int, input().split())

    max_n = max(N, F)
    log_fact = [0.0] * (max_n + 1)
    for i in range(1, max_n + 1):
        log_fact[i] = log_fact[i-1] + math.log(i)

    expectation = 0.0

    for x in range(1, F+1):
        px = 0.0
        if x < F:
            m = F - x
            max_s = min(K-1, N)
            for s in range(0, max_s + 1):
                remaining = N - s
                if remaining < 0:
                    continue
                if x == 1:
                    t = remaining
                    u = 0
                    lower_t = max(K - s, 1)
                    if t < lower_t:
                        continue
                    if s == 0:
                        log_comb_N_s = 0.0
                    else:
                        log_comb_N_s = log_fact[N] - log_fact[s] - log_fact[N - s]
                    log_comb_remaining_t = log_fact[remaining] - log_fact[t] - log_fact[remaining - t]
                    part_ms = s * math.log(m) if (m != 0 or s == 0) else -math.inf
                    part_x = u * math.log(x-1) if (x != 1 or u != 0) else 0.0
                    term_log = log_comb_N_s + log_comb_remaining_t + part_ms + part_x - N * math.log(F)
                    term = math.exp(term_log) if term_log != -math.inf else 0.0
                    px += term
                else:
                    lower_t = max(K - s, 1)
                    upper_t = remaining
                    if lower_t > upper_t:
                        continue
                    sum_t = 0.0
                    for t in range(lower_t, upper_t + 1):
                        u = remaining - t
                        if x == 1 and u != 0:
                            continue
                        if s == 0:
                            log_comb_N_s = 0.0
                        else:
                            log_comb_N_s = log_fact[N] - log_fact[s] - log_fact[N - s]
                        if remaining == 0 and t == 0:
                            log_comb_remaining_t = 0.0
                        else:
                            log_comb_remaining_t = log_fact[remaining] - log_fact[t] - log_fact[remaining - t]
                        part_ms = s * math.log(m) if m != 0 or s == 0 else -math.inf
                        part_x = 0.0
                        if x > 1:
                            part_x = u * math.log(x - 1)
                        term_log = log_comb_N_s + log_comb_remaining_t + part_ms + part_x - N * math.log(F)
                        if term_log == -math.inf:
                            term = 0.0
                        else:
                            term = math.exp(term_log)
                        sum_t += term
                    px += sum_t
        else:
            s = 0
            max_s_val = min(K-1, N)
            if s > max_s_val:
                continue
            remaining = N - s
            lower_t = max(K - s, 1)
            upper_t = remaining
            if lower_t > upper_t:
                continue
            sum_t = 0.0
            for t in range(lower_t, upper_t + 1):
                u = remaining - t
                log_comb = log_fact[N] - log_fact[t] - log_fact[N - t]
                term_log = log_comb - math.log(F) * N
                if F - 1 > 0:
                    term_log += u * math.log(F - 1)
                term = math.exp(term_log)
                sum_t += term
            px += sum_t

        expectation += x * px

    print("{0:.15f}".format(expectation))

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