結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー rin204
提出日時 2025-02-05 22:31:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 2,396 bytes
コンパイル時間 795 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 77,952 KB
最終ジャッジ日時 2025-02-05 22:31:38
合計ジャッジ時間 4,624 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, MOD = map(int, input().split())

# i 人目以降の成功数
dp_y = [[0] * 3 for _ in range(n + 1)]
# i 人目以降の投げない数
dp_z = [[0] * 3 for _ in range(n + 1)]
inv_2 = pow(2, -1, MOD)
inv_4 = inv_2 * inv_2 % MOD

for i in range(n - 1, -1, -1):
    dp_y[i][0] = dp_y[i + 1][1]
    dp_z[i][0] = dp_z[i + 1][1] + 1

    dp_y[i][1] = (dp_y[i + 1][2] * inv_2 + (dp_y[i + 1][0] + 1 + dp_y[i + 1][1]) * inv_4) % MOD
    dp_z[i][1] = ((dp_z[i + 1][2] + 1) * inv_2 + (dp_z[i + 1][0] + dp_z[i + 1][1]) * inv_4) % MOD

    dp_y[i][2] = (dp_y[i + 1][1] + 1 + dp_y[i + 1][2]) * inv_2 % MOD
    dp_z[i][2] = (dp_z[i + 1][1] + dp_z[i + 1][2]) * inv_2 % MOD

prob = [[0] * 3 for _ in range(n + 1)]
prob[0][1] = 1
ans = [0] * n
cum = [0] * (n + 1)

for i in range(n):
    if i > 0:
        cum[i] += cum[i - 1]
        cum[i] %= MOD

    prob[i][0] %= MOD
    prob[i][1] %= MOD
    prob[i][2] %= MOD

    # 投げない
    c = 1
    prob[i + 1][1] += prob[i][0]
    c += cum[i]  # 直前までで成功
    c += (i - cum[i] - 1) * inv_2 % MOD  # 直前までで投げない
    c += dp_y[i + 1][1]  # 以降で成功

    ans[i] += c * prob[i][0] % MOD

    # （どちらでも）
    c = 1
    # （どちらでも）-> 投げる
    prob[i + 1][0] += prob[i][1] * inv_4 % MOD
    prob[i + 1][1] += prob[i][1] * inv_4 % MOD
    c += cum[i] * inv_2 % MOD  # 直前までで成功
    c += (i - cum[i]) * inv_4 % MOD  # 自身が失敗・直前までで投げない
    c += (dp_y[i + 1][0] + dp_z[i + 1][0]) * inv_4 % MOD  # 自身が失敗・以降で成功 or 投げない
    cum[i + 1] += prob[i][1] * inv_4 % MOD

    # （どちらでも）-> 投げない
    prob[i + 1][2] += prob[i][1] * inv_2 % MOD
    c += cum[i] * inv_2 % MOD  # 直前までで成功
    c += (i - cum[i]) * inv_4 % MOD  # 直前までで投げない
    c += dp_y[i + 1][2] * inv_2 % MOD  # 以降で成功

    ans[i] += c * prob[i][1] % MOD

    # 投げる
    c = 1
    prob[i + 1][1] += prob[i][2] * inv_2 % MOD
    prob[i + 1][2] += prob[i][2] * inv_2 % MOD
    c += cum[i]  # 直前までで成功
    c += (i - cum[i]) * inv_2 % MOD  # 自身が失敗・直前までで投げない
    c += (dp_y[i + 1][1] + dp_z[i + 1][1]) * inv_2 % MOD  # 自身が失敗・以降で成功 or 投げない
    cum[i + 1] += prob[i][2] * inv_2 % MOD

    ans[i] += c * prob[i][2] % MOD

    ans[i] %= MOD


print(*ans)
0