結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー suisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
}
0