Atcoder ABC 333 F - Bomb Game 2

题目大意（采用0#语言）：有n个人，每个人每次要么被“炸掉”，要么就被移到最后面去，概率都是1/2，求最后只剩下初始时排名为第i的人的概率。

这道题跟人数有关，而且跟位置有关。

我们定义dp[i]表示一共有i个人，第i个为最后一位留下来时的概率。

（不想写公式）

定义j从0到i - 1，表示从前面i - 1个人里面选择j个人“炸掉”

ans[i] = 从i - 1里面选择j个人的方案数  * (1 / 2ⁱ) * dp[n - j]

1 / 2ⁱ表示每次炸掉前面j个人并且将第i个人移到最后一个去的可能性。那么一共还剩下n - j个人，i在最后面，在乘上这个可能性就可以了。

我们会发现，dp[i]这个神奇的东西，和数量有关，方案数的移动也总是和数有着联系，位置在变，但是数没有变。

我们已经知道如何求解正确的答案了，那么我们接下来怎么求出dp[i]呢？

现在有多种情况

(1)i位置的前面i - 1个数全部都被“炸掉”，也就是说i已经成为剩下的最后一个数字，不能操作了，答案是1 / 2^{i - 1}

(2)i位置前面的i - 1个数一个都没有被炸掉，那么答案就是2ⁱ * dp[i]（现在i又被移到了最后一个位置上面去）

想到这里，我不禁思考一个问题，就是i永远都不成为最后一个留下的数字，这些操作有可能会一直进行下去，是的，这也是一种概率。硬要我解释的话，可能就是找到那些有尽的概率吧，无穷的概率谁也说不清楚了。

(3)i位置前面i - 1个数字中选出j个数字(1 <= j <= i - 2)炸掉，dp[i] += 从i个数字里面选出j个数字的方案数 * (1 / 2ⁱ) * 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 ;
}