結果
問題 | No.3055 Simple Chicken Game |
ユーザー |
|
提出日時 | 2025-01-18 16:09:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 277 ms / 2,000 ms |
コード長 | 4,056 bytes |
コンパイル時間 | 3,028 ms |
コンパイル使用メモリ | 90,372 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-02-05 00:27:33 |
合計ジャッジ時間 | 4,791 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
// correct #include <array> #include <cassert> #include <iostream> #include <vector> #include <atcoder/modint> using mint = atcoder::modint; std::vector<mint> solve(int n) { const mint inv2 = mint(2).inv(), inv4 = mint(4).inv(); std::vector f(3, std::vector(n, std::array<std::array<mint, 2>, 3>{})); constexpr int OFFSET = 1; for (int start_d = -1; start_d <= 1; ++start_d) { auto& fdp = f[start_d + OFFSET]; fdp[0][start_d + OFFSET] = { 1, 0 }; for (int i = 0; i < n - 1; ++i) { auto& ndp = fdp[i + 1]; for (int d = -1; d <= 1; ++d) { const auto& [p, h] = fdp[i][d + OFFSET]; // d := c_2 - c_0 if (d < 0) { // head ndp[d + 0 + OFFSET][0] += p * inv2; ndp[d + 0 + OFFSET][1] += h * inv2 + p * inv2; // tail ndp[d + 1 + OFFSET][0] += p * inv2; ndp[d + 1 + OFFSET][1] += h * inv2; } else if (d > 0) { // nop ndp[d - 1 + OFFSET][0] += p; ndp[d - 1 + OFFSET][1] += h; } else { // nop ndp[d - 1 + OFFSET][0] += p * inv2; ndp[d - 1 + OFFSET][1] += h * inv2; // head ndp[d + 0 + OFFSET][0] += p * inv4; ndp[d + 0 + OFFSET][1] += h * inv4 + p * inv4; // tail ndp[d + 1 + OFFSET][0] += p * inv4; ndp[d + 1 + OFFSET][1] += h * inv4; } } } } std::vector H(3, std::vector<mint>(n)); for (int start_d = -1; start_d <= 1; ++start_d) { for (int i = 0; i < n; ++i) { for (int end_d = -1; end_d <= 1; ++end_d) { H[start_d + OFFSET][i] += f[start_d + OFFSET][i][end_d + OFFSET][1]; } assert(H[start_d + OFFSET][i] == mint(i) / 3 - (mint(1) / 3 + start_d) * (mint(4).pow(i) - 1) / (3 * mint(4).pow(i))); } } const auto& T = H; std::vector P(1, std::array<mint, 3>{}); P[0][0 + OFFSET] = 1; std::vector<mint> R(n, 1); for (int s = 0; s < n; ++s) { const int r = n - 1 - s; std::vector nxt_P(s + 2, std::array<mint, 3>{}); for (int x = 0; x <= s; ++x) { for (int d = -1; d <= 1; ++d) { const int z = x + d; const int y = s - x - z; const mint p = P[x][d + OFFSET]; if (p == 0) { // skip invalid states (e.g. min(x,y,z)<0) continue; } if (d == -1) { // head R[s] += p * inv2 * y; nxt_P[x][-1 + OFFSET] += p * inv2; // tail R[s] += p * inv2 * (n - 1 - T[0 + OFFSET][r]); nxt_P[x][0 + OFFSET] += p * inv2; } else if (d == 1) { // nop R[s] += p * (x + y + H[0 + OFFSET][r]); nxt_P[x + 1][0 + OFFSET] += p; } else { // nop R[s] += p * inv2 * (x + y + H[-1 + OFFSET][r]); nxt_P[x + 1][-1 + OFFSET] += p * inv2; // head R[s] += p * inv4 * y; nxt_P[x][0 + OFFSET] += p * inv4; // tail R[s] += p * inv4 * (n - 1 - T[1 + OFFSET][r]); nxt_P[x][1 + OFFSET] += p * inv4; } } } P.swap(nxt_P); } return R; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, p; std::cin >> n >> p; mint::set_mod(p); std::vector<mint> R = solve(n); for (int i = 0; i < n; ++i) { if (i != 0) std::cout << ' '; std::cout << R[i].val(); } std::cout << std::endl; }