题目大意（采用0#语言）：有n个人，每个人每次要么被“炸掉”，要么就被移到最后面去，概率都是1/2，求最后只剩下初始时排名为第i的人的概率。
这道题跟人数有关，而且跟位置有关。
我们定义dp[i]表示一共有i个人，第i个为最后一位留下来时的概率。
（不想写公式）
定义j从0到i - 1，表示从前面i - 1个人里面选择j个人“炸掉”
ans[i] = 从i - 1里面选择j个人的方案数 * (1 / 2i) * dp[n - j]
1 / 2i表示每次炸掉前面j个人并且将第i个人移到最后一个去的可能性。那么一共还剩下n - j个人，i在最后面，在乘上这个可能性就可以了。
我们会发现，dp[i]这个神奇的东西，和数量有关，方案数的移动也总是和数有着联系，位置在变，但是数没有变。
我们已经知道如何求解正确的答案了，那么我们接下来怎么求出dp[i]呢？
现在有多种情况
(1)i位置的前面i - 1个数全部都被“炸掉”，也就是说i已经成为剩下的最后一个数字，不能操作了，答案是1 / 2i - 1
(2)i位置前面的i - 1个数一个都没有被炸掉，那么答案就是2i * dp[i]（现在i又被移到了最后一个位置上面去）
想到这里，我不禁思考一个问题，就是i永远都不成为最后一个留下的数字，这些操作有可能会一直进行下去，是的，这也是一种概率。硬要我解释的话，可能就是找到那些有尽的概率吧，无穷的概率谁也说不清楚了。
(3)i位置前面i - 1个数字中选出j个数字(1 <= j <= i - 2)炸掉，dp[i] += 从i个数字里面选出j个数字的方案数 * (1 / 2i) * dp[i - j]
我们知道dp[1] = 1, 从i = 2开始dp。
另外对于(2)的情况，dp[i]是未知的，有一种常见的思路，就是把dp[i]进行移项变成 dp[i] * (1 + (...)) = ...的形式，然后把(1 + (...))移到右边去变成除法就可以啦！
#include <bits/stdc++.h> using namespace std ; typedef long long ll ; const ll mod = 998244353 ; const int N = 3005 ; int n ; ll dp[N], a[N], ni[N], ans[N], er[N], fac[N], rev[N] ; ll Quick(ll a, int b) { ll res = 1 ; while(b) { if(b & 1) res = res * a % mod ; a = a * a % mod ; b >>= 1 ; } return res ; } ll C(int a, int b) { if(b == 0) return 1ll ; return fac[a] * rev[b] % mod * rev[a - b] % mod ; } int main() { scanf("%d", &n) ; ni[0] = 1, er[0] = 1 ; fac[0] = 1 ; for(int i = 1; i <= n; i ++) ni[i] = (ni[i - 1] << 1) % mod, er[i] = (er[i - 1] << 1) % mod, fac[i] = fac[i - 1] * i % mod ; for(int i = 1; i <= n; i ++) { ni[i] = Quick(ni[i] - 1, mod - 2) ; er[i] = Quick(er[i], mod - 2) ; } rev[n] = Quick(fac[n], mod - 2) ; for(int i = n; i >= 1; i --) rev[i - 1] = rev[i] * i % mod ; dp[1] = 1 ; for(int i = 2; i <= n; i ++) { dp[i] = 2 * ni[i] % mod ; for(int j = 1; j <= i - 2; j ++) { dp[i] = (dp[i] + C(i - 1, j) * dp[i - j] % mod * ni[i] % mod) % mod ; } } ans[n] = dp[n] ; for(int i = 1; i <= n - 1; i ++) { for(int j = 0; j <= i - 1; j ++) { ans[i] = (ans[i] + C(i - 1, j) * er[i] % mod * dp[n - j] ) % mod ; } } for(int i = 1; i <= n; i ++) { printf("%lld ", ans[i]) ; } return 0 ; }