結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
![]() |
提出日時 | 2025-06-07 08:59:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,837 ms / 2,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 2,012 ms |
コンパイル使用メモリ | 200,780 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-07 08:59:26 |
合計ジャッジ時間 | 13,778 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint.hpp> using namespace std; using i32 = int; using i64 = long long; using f64 = long double; using i128 = __int128_t; using p2 = pair<i64, i64>; using el = tuple<i64, i64, i64>; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) { res = res * t; } t = t * t; } return res; } void _main() { vector<mint> fac(10000, 1), finv(10000, 1), inv(10000, 0); inv[1] = 1; i64 mod = 998244353; for (i64 i = 2; i < fac.size(); i++) { fac[i] = fac[i - 1] * i; inv[i] = -inv[mod % i] * (mod / i); finv[i] = finv[i - 1] * inv[i]; } i64 n; cin >> n; vector<pair<mint, mint>> dp(n + 1); vector<mint> ans(n + 1, 0); vector<mint> e(n + 1, 0), p(n + 1, 0); p[n] = 1; for (i64 i = n; i >= 1; i--) { mint sum = 0; for (i64 j = 1; j < i; j++) { sum += fac[i] * finv[j] * finv[i - j]; } for (i64 j = 1; j < i; j++) { p[j] += p[i] * fac[i] * finv[j] * finv[i - j] / sum; } for (i64 j = i + 1; j <= n; j++) { ans[i] += e[j] * p[j]; } if (i == 1) break; e[i] = mint(3).pow(i) / (mint(2).pow(i) * 3 - 6); } for (i64 i = 1; i <= n; i++) { cout << ans[i].val() << " "; } cout << "\n"; }