ABC
不讲
D
待更
E
待更
F
设 $ f(i, j) $ 为有 $ i $ 个人时，第 $ j $ 个人活到最后的概率，显然：
\[
f(i, j) = \begin{cases}
1, & i = 1, j = 1 \\
\frac{1}{2}f(i, i), & i \neq 1, j = 1 \\
\frac{1}{2}f(i, j - 1) + \frac{1}{2}f(i - 1, j - 1), & i \neq 1, 2 \le j \le i
\end{cases}
\]
但是这个转移方程有后效性。
观察转移方程，可以发现 $ i $ 是没有后效性的，于是可以用 DP 套高斯消元的方法解。
我们将 $ f(i, 1), f(i, 2), \cdots, f(i, i) $ 视作未知数，将 $ f(i - 1, 1), f(i - 1, 2), \cdots, f(i - 1, i - 1) $ 视作已知数，可以得到 $ i $ 元一次方程：
\[
\begin{cases}
-f(i, 1) + \frac{1}{2}f(i, i) = 0 \\
-f(i, 2) + \frac{1}{2}f(i, 1) = -\frac{1}{2}f(i - 1, 1) \\
-f(i, 3) + \frac{1}{2}f(i, 2) = -\frac{1}{2}f(i - 1, 2) \\
\cdots \\
-f(i, i) + \frac{1}{2}f(i, i - 1) = -\frac{1}{2}f(i - 1, i - 1)
\end{cases}
\]
于是就可以愉快的高斯消元了。但是如果用一般的高斯消元，高斯消元的时间复杂度是 $ O(n ^ 3) $，总的时间复杂度是 $ O(n ^ 4) $。
把增广矩阵拎出来康康：（以 $ i = 5 $ 为例）
\[
\left[
\begin{array}{ccccc|c}
-1 & 0 & 0 & 0 & \frac{1}{2} & 0 \\
\frac{1}{2} & -1 & 0 & 0 & 0 & -\frac{1}{2}f(4, 1) \\
0 & \frac{1}{2} & -1 & 0 & 0 & -\frac{1}{2}f(4, 2) \\
0 & 0 & \frac{1}{2} & -1 & 0 & -\frac{1}{2}f(4, 3) \\
0 & 0 & 0 & \frac{1}{2} & -1 & -\frac{1}{2}f(4, 4)
\end{array}
\right]
\]
观察得知每行只有 $ 2 $ 个位置要消元，所以可以在 $ O(n) $ 的时间内高斯消元。
具体做法：用第 $ k $ 行减第 $ k + 1 $ 行，消完元后矩阵将只有对角线和最后一列有数，把第 $ i $ 列的数减掉就可以了。
注：$ -1 \equiv 998244352 \pmod{998244353} $ ，$ \frac{1}{2} \equiv 499122177 \pmod{998244353} $ ，$ -\frac{1}{2} \equiv 499122176 \pmod{998244353} $ 。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
ll f[3005][3005];
ll a[3005][3005], b[3005];
ll qpow(ll a, ll x, ll m) {
ll ans = 1;
while (x) {
if (x & 1) {
ans = ans * a % m;
}
x >>= 1;
a = a * a % m;
}
return ans;
}
void multiply_by_and_subtract(int x, ll k, int y, int n) {
a[y][x] = (a[x][x] * k % mod + mod - a[y][x]) % mod;
a[y][y] = (a[x][y] * k % mod + mod - a[y][y]) % mod;
if (y != n) {
a[y][n] = (a[x][n] * k % mod + mod - a[y][n]) % mod;
}
b[y] = (b[x] * k % mod + mod - b[y]) % mod;
}
#define decrease multiply_by_and_subtract
void gauss(int n) {
for (int i = 1; i <= n; i++) {
a[i][i] = 998244352, a[i][(i - 1) ? (i - 1) : (n)] = 499122177;
b[i] = f[n - 1][i - 1] * 499122176 % mod;
}
for (int i = 1; i < n; i++) {
decrease(i, a[i + 1][i] * qpow(a[i][i], mod - 2, mod) % mod, i + 1, n);
}
b[n] = b[n] * qpow(a[n][n], mod - 2, mod) % mod;
a[n][n] = 1;
for (int i = 1; i < n; i++) {
b[i] = (b[i] - a[i][n] * b[n] % mod + mod) % mod;
b[i] = b[i] * qpow(a[i][i], mod - 2, mod) % mod;
a[i][n] = 0;
}
}
int main() {
int n;
scanf("%d", &n);
f[1][1] = 1;
for (int i = 2; i <= n; i++) {
gauss(i);
for (int j = 1; j <= n; j++) {
f[i][j] = b[j];
}
}
for (int i = 1; i <= n; i++) {
printf("%lld ", f[n][i]);
}
}