結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー emthrm
提出日時 2025-02-09 04:09:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,706 bytes
コンパイル時間 1,451 ms
コンパイル使用メモリ 96,404 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-09 04:10:38
合計ジャッジ時間 2,037 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

#include <atcoder/modint>
using mint = atcoder::modint;

mint H(const int k, const int d) {
  return mint::raw(k) / 3 - (mint::raw(1) / 3 + d) * (mint::raw(4).pow(k) - 1) / (3 * mint::raw(4).pow(k));
}

// プレイヤー i (0-based) の順位の期待値を考える。
// プレイヤー i より先に操作したプレイヤーによる順位の寄与は以下の式で表せる。
// - d = -1 のとき P'(i-1, x_0, -1) (x_1 + (x_0 + x_-1) / 2)
//                 = P'(i-1, x_0, -1) (x_1 + (i - x_1) / 2)
//                 = P'(i-1, x_0, -1) (x_1 / 2 + i / 2)
// - d = 0 のとき P'(i-1, x_0, 0) ((x_1 + (x_0 + x_-1) / 2) / 2 + (x_1 + x_0) / 2)
//                = P'(i-1, x_0, 0) ((x_1 / 2 + i / 2) / 2 + (x_1 / 2 + i / 2) / 2)
//                = P'(i-1, x_0, 0) (x_1 / 2 + i / 2)
// - d = 1 のとき P'(i-1, x_0, 1) (x_1 + x_0)
//                = P'(i-1, x_0, 1) (x_1 + (i - (x_-1 - x_0) - x_1) / 2)
//                = P'(i-1, x_0, 1) (x_1 + (i - 1 - x_1) / 2)
//                = P'(i-1, x_0, 1) (x_1 / 2 + (i - 1) / 2)
// これらの和は x_1 / 2 + P'(i-1, x_0, -1) * i / 2 + P'(i-1, x_0, 0) * i / 2 + P'(i-1, x_0, 1) * (i - 1) / 2 になる。
// よって P' は x_0 に依存せず計算してよい。
// 後に操作するプレイヤーからの寄与は解説と同様に i, H のみの式で表せる。
int main () {
  constexpr int kMaxN = 3000, kMinP = 100000000, kMaxP = 1000000000;

  int n, P;
  std::cin >> n >> P;
  assert(1 <= n && n <= kMaxN);
  assert(kMinP <= P && P <= kMaxP);
  mint::set_mod(P);

  constexpr int kOffset = 1;
  std::vector prob(3, mint());
  prob[kOffset] = mint::raw(1);
  mint h_exp = 0;
  for (int i = 0; i < n; ++i) {
    std::vector prob_nxt(3, mint());
    mint h_exp_nxt = h_exp;

    mint ans = 1 + h_exp / 2;
    // d = -1: コインを投げる
    ans += prob[-1 + kOffset] * (mint(i) / 2 + (n - 1 - i - H(n - 1 - i, 0)) / 2);
    prob_nxt[-1 + kOffset] += prob[-1 + kOffset] / 2;
    prob_nxt[kOffset] += prob[-1 + kOffset] / 2;
    h_exp_nxt += prob[-1 + kOffset] / 2;
    // d = 0: どちらでもよい
    ans += prob[kOffset] * (mint(i) / 2 + H(n - 1 - i, -1) / 2 + (n - 1 - i - H(n - 1 - i, 1)) / 4);
    prob_nxt[-1 + kOffset] += prob[kOffset] / 2;
    prob_nxt[kOffset] += prob[kOffset] / 4;
    prob_nxt[1 + kOffset] += prob[kOffset] / 4;
    h_exp_nxt += prob[kOffset] / 4;
    // d = 1: コインを投げない
    ans += prob[1 + kOffset] * (mint(i - 1) / 2 + H(n - 1 - i, 0));
    prob_nxt[kOffset] += prob[1 + kOffset];

    std::cout << ans.val() << " \n"[i + 1 == n];
    prob.swap(prob_nxt);
    std::swap(h_exp, h_exp_nxt);
  }
  return 0;
}
0