結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
|
提出日時 | 2025-06-14 04:49:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,012 bytes |
コンパイル時間 | 2,272 ms |
コンパイル使用メモリ | 218,316 KB |
実行使用メモリ | 16,068 KB |
最終ジャッジ日時 | 2025-06-14 04:49:29 |
合計ジャッジ時間 | 6,112 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 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]; int dp[N], 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) { if (i == 1) return 0; if (setDP[i]) return dp[i]; int curr = 0, c = 0, cj = 0; for (int j = 1; j < i; j++) { fillDP(j); cj = inv(power(3, i - 1)) * nCr(i, j); cj %= MOD; curr += cj * dp[j]; curr %= MOD; c += cj; c %= MOD; } curr += 1; curr %= MOD; curr *= inv(c); curr %= MOD; setDP[i] = true; dp[i] = curr; return curr; } void solve() { int n; cin >> n; fillDP(n); // dp[i] = operations from i to 1 // ans[i] = operations from n to <=i = (1 / i) * sum{j = 1 to i}(operations from n to 1 - operations from j to 1) vi ans(n + 1, 0); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) { ans[i] += (dp[n] - dp[j] + MOD); ans[i] %= MOD; ans[i] *= inv(i); ans[i] %= MOD; } for (int i = 1; i <= n; i++) cout << ans[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; }