結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー suisen
提出日時 2025-01-18 16:10:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 866 ms / 2,000 ms
コード長 2,397 bytes
コンパイル時間 2,789 ms
コンパイル使用メモリ 83,596 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-05 00:27:46
合計ジャッジ時間 7,113 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

// correct

#include <array>
#include <cassert>
#include <iostream>
#include <vector>
#include <atcoder/modint>

using mint = atcoder::modint;

mint inv2, inv3, inv4;

mint H(int i, int d) {
    static std::vector<mint> pow_inv4{ 1 };
    for (int siz = pow_inv4.size(); siz <= i; ++siz) {
        mint nxt_pow = pow_inv4.back() * inv4;
        pow_inv4.push_back(nxt_pow);
    }
    return i * inv3 - (inv3 + d) * (1 - pow_inv4[i]) * inv3;
}
mint T(int i, int d) {
    return H(i, d);
}

std::vector<mint> solve(int n) {
    constexpr int OFFSET = 1;

    // max x s.t. x+(x-1) <= i
    constexpr auto max_x = [](int i) -> int { return (i + 1) / 2; };

    std::vector P(max_x(0) + 1, std::vector<mint>(3));
    P[0][0 + OFFSET] = 1;
    std::vector<mint> R(n, 1);
    for (int i = 0; i < n; ++i) {
        std::vector nxt_P(max_x(i + 1) + 1, std::vector<mint>(3));
        for (int x = 0; x <= max_x(i); ++x) for (int d = -1; d <= 1; ++d) {
            const int z = x + d, y = i - 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[i] += p * inv2 * y;
                nxt_P[x][-1 + OFFSET] += p * inv2;
                // tail
                R[i] += p * inv2 * (n - 1 - T(n - 1 - i, 0));
                nxt_P[x][0 + OFFSET] += p * inv2;
            } else if (d == 1) {
                // nop
                R[i] += p * (x + y + H(n - 1 - i, 0));
                nxt_P[x + 1][0 + OFFSET] += p;
            } else {
                // nop
                R[i] += p * inv2 * (x + y + H(n - 1 - i, -1));
                nxt_P[x + 1][-1 + OFFSET] += p * inv2;
                // head
                R[i] += p * inv4 * y;
                nxt_P[x][0 + OFFSET] += p * inv4;
                // tail
                R[i] += p * inv4 * (n - 1 - T(n - 1 - i, 1));
                nxt_P[x][1 + OFFSET] += p * inv4;
            }
        }
        P.swap(nxt_P);
    }
    return R;
}

int main() {
    int n, p;
    std::cin >> n >> p;
    mint::set_mod(p);
    inv2 = mint(1) / 2;
    inv3 = mint(1) / 3;
    inv4 = mint(1) / 4;
    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