結果
問題 | No.3055 Simple Chicken Game |
ユーザー |
👑 |
提出日時 | 2025-02-05 21:44:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 3,714 bytes |
コンパイル時間 | 4,613 ms |
コンパイル使用メモリ | 289,016 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-02-05 22:52:55 |
合計ジャッジ時間 | 6,460 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #include "atcoder/modint.hpp" using mint = atcoder::modint; void solve() { int n; std::cin >> n; int P; std::cin >> P; mint::set_mod(P); mint inv2 = mint(1) / 2; mint inv4 = inv2 * inv2; // dp[i] := i 番目のプレイヤーの手番、(投げない - 失敗 + 1) = j の時の i 人目以降の(成功、投げない) の回数の期待値 std::vector<std::vector<std::pair<mint, mint>>> dp(n + 1, std::vector<std::pair<mint, mint>>(3, {0, 0})); for (int i = n - 1; i >= 0; i--) { // j = 0 -> 投げない dp[i][0].first = dp[i + 1][1].first; dp[i][0].second = dp[i + 1][1].second + 1; // j = 1 -> どちらでも dp[i][1].first = dp[i + 1][2].first * inv2 + (dp[i + 1][0].first + 1 + dp[i + 1][1].first) * inv4; dp[i][1].second = (dp[i + 1][2].second + 1) * inv2 + (dp[i + 1][0].second + dp[i + 1][1].second) * inv4; // j = 2 -> 投げる dp[i][2].first = (dp[i + 1][1].first + 1 + dp[i + 1][2].first) * inv2; dp[i][2].second = (dp[i + 1][1].second + dp[i + 1][2].second) * inv2; } std::vector<std::vector<mint>> prob(n + 1, std::vector<mint>(3, 0)); prob[0][1] = 1; std::vector<mint> ans(n, 0); // i - 1 人目までで成功した人数の期待値 // 順位の導出式を眺めると、(投げない - 失敗) の値に関わらず cum[i] + (i - cum[i]) / 2 が順位に加算されるのでそのまま使える std::vector<mint> cum(n + 1, 0); for (int i = 0; i < n; i++) { if (i != 0) { cum[i] += cum[i - 1]; } // j = 0 -> 投げない { prob[i + 1][1] += prob[i][0]; mint c = 1; c += cum[i]; // 直前までで成功 c += mint(i - cum[i] - 1) * inv2; // 直前までで投げない c += dp[i + 1][1].first; // 以降で成功 ans[i] += prob[i][0] * c; } // j = 1 -> どちらでも { mint c = 1; // 投げる prob[i + 1][0] += prob[i][1] * inv4; prob[i + 1][1] += prob[i][1] * inv4; c += cum[i] * inv2; // 直前までで成功 c += mint(i - cum[i]) * inv4; // 自身が失敗・直前までで投げない c += (dp[i + 1][0].first + dp[i + 1][0].second) * inv4; // 自身が失敗・以降で成功 or 投げない cum[i + 1] += prob[i][1] * inv4; // 投げない prob[i + 1][2] += prob[i][1] * inv2; c += cum[i] * inv2; // 直前までで成功 c += mint(i - cum[i]) * inv4; // 直前までで投げない c += dp[i + 1][2].first * inv2; // 以降で成功 ans[i] += prob[i][1] * c; } // j = 2 -> 投げる { mint c = 1; prob[i + 1][1] += prob[i][2] * inv2; prob[i + 1][2] += prob[i][2] * inv2; c += cum[i]; // 直前までで成功 c += mint(i - cum[i]) * inv2; // 自身が失敗・直前までで投げない c += (dp[i + 1][1].first + dp[i + 1][1].second) * inv2; // 自身が失敗・以降で成功 or 投げない cum[i + 1] += prob[i][2] * inv2; ans[i] += prob[i][2] * c; } } for (size_t i = 0; i < ans.size(); i++) { std::cout << ans[i].val() << (i + 1 == ans.size() ? '\n' : ' '); } } int main(int argc, char *argv[]) { std::cin.tie(0)->sync_with_stdio(0); solve(); }