結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー yuppe19 😺
提出日時 2015-04-28 22:46:35
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 157 ms / 5,000 ms
コード長 1,137 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 144 ms
コンパイル使用メモリ 77,600 KB
最終ジャッジ日時 2025-12-03 14:50:27
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/python
N = int(1e6)
E = [0, 1., 1.0833333333333333, 1.2569444444444444, 1.5353009259259260, 1.6915991512345676, 2.0513639724794235] + [0] * N
p = [0] * 7
# 1 + p1
p[1] = E[2] - 1
# 1 + p1**2 + p1 + p2
p[2] = E[3] - p[1] - p[1]**2 - 1
# 1 + p1**3 + p1**2 + 2p1p2 + p1 + p2 + p3
p[3] = E[4] - p[1] - p[1]**2 - p[1]**3 - 2*p[1]*p[2] - p[2] - 1
# 1 + p1**4 + p1**3 + 3(p1**2)p2 + p1**2 + p2**2 + 2p1p2 + 2p1p3 + p1 + p2 + p3 + p4
p[4] = E[5] - p[1]**4 - p[1]**3 - 3*(p[1]**2)*p[2] - p[1]**2 - p[1] - 2*p[1]*p[2] - p[2]**2 - 2*p[1]*p[3] - p[2] - p[3] - 1
# 1 + p1**5 + p1**4 + 4(p1**3)p2 + 3(p1**2)p2 + 3(p1**2)p3 + 3p1(p2**2) + p1**3 + p1**2 + p2**2 + 2p1p4 + 2p1p2 + 2p1p3 + 2p2p3 + p1 + p2 + p3 + p4 + p5
p[5] = E[6] - p[1]**5 - p[1]**4 - 4*(p[1]**3)*p[2] - p[1]**3 - 3*(p[1]**2)*p[2] - 3*(p[1]**2)*p[3] - 3*p[1]*(p[2]**2) - p[1]**2 - p[2]**2 - 2*p[1]*p[2] - 2*p[2]*p[3] - 2*p[1]*p[4] - 2*p[1]*p[3] - p[1] - p[2] - p[3] - p[4] - 1
p[6] = 1 - sum(p[:6])

for x in xrange(7, N+1):
    E[x] = 1
    for i in xrange(6):
        E[x] += E[x-i-1]*p[i+1]
t = int(raw_input())
for _ in xrange(t):
    n = int(raw_input())
    print E[n]
0