結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
|
提出日時 | 2025-06-14 05:57:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,764 bytes |
コンパイル時間 | 2,433 ms |
コンパイル使用メモリ | 217,924 KB |
実行使用メモリ | 8,256 KB |
最終ジャッジ日時 | 2025-06-14 05:57:23 |
合計ジャッジ時間 | 5,957 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 TLE * 1 -- * 15 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int int64_t template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define pi pair<int, int> #define vi vector<int> #define pb push_back #define all(x) (x).begin(), (x).end() template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &x : v) in >> x; return in; } template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) { for (const auto &x : v) out << x << ' '; return out; } template <typename T1, typename T2> istream &operator>>(istream &in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; } template <typename T1, typename T2> ostream &operator<<(ostream &out, const pair<T1, T2> &p) { out << p.first << ' ' << p.second; return out; } const int MOD = 998244353; const int N = 5001; bool setDP[N][N]; int dp[N][N]; int factorial[N], invfactorial[N]; int power(int a, int b) { a %= MOD; int res = 1; while (b > 0) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res; } int inv(int x) { x %= MOD; return (power(x, MOD - 2) % MOD); } void fillfactorial() { factorial[0] = 1; for (int i = 1; i < N; i++) factorial[i] = (factorial[i - 1] * i) % MOD; invfactorial[N - 1] = inv(factorial[N - 1]); for (int i = N - 1; i > 1; i--) invfactorial[i - 1] = (invfactorial[i] * i) % MOD; invfactorial[0] = 1; } int nCr(int n, int r) { int ans = 1; ans *= factorial[n]; ans %= MOD; ans *= invfactorial[r]; ans %= MOD; ans *= invfactorial[n - r]; ans %= MOD; return ans; } int fillDP(int i, int j) { if (i <= j) return 0; if (setDP[i][j]) return dp[i][j]; int total = 0, currcoeff = 0, totalcoeff = 0; for (int k = 1; k <= i - 1; k++) { fillDP(k, j); currcoeff = inv(power(3, i - 1)) * nCr(i, k); currcoeff %= MOD; total += (currcoeff * dp[k][j]); total %= MOD; totalcoeff += currcoeff; totalcoeff %= MOD; } total += 1; total *= inv(totalcoeff); total %= MOD; setDP[i][j] = true; dp[i][j] = total; return dp[i][j]; } void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) fillDP(n, i); for (int i = 1; i <= n; i++) cout << dp[n][i] << ' '; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; fillfactorial(); while (t--) solve(); return 0; }