Codeforces 1156F (概率DP)

Codeforces 1156F
题意：包里面有$n$个数，每次取一个数，当前取出的数为$x$，前一个取出的数为$y$,则：
若x > y，游戏继续
若x = y，游戏结束并且玩家赢
若x < y，游戏结束并且玩家输
问玩家赢的概率

容易发现必须从小取到大。
设$dp(i,j)$为删了$i$个卡牌，最大删到$j$值卡牌获胜的概率。
那么考虑取出相同值或者大于$j$值卡牌的情况，两者概率相加。具体转移方程可以看代码。
代码实现中加入一个$0$必选，不影响答案，可以方便求出答案，答案为$dp[0][0]$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 998244353;

    LL ksm(LL a, LL b) {
        LL ret = 1, bs = a;
        while (b) {
            if (b & 1) ret = (ret * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ret;
    }

    LL n, a[5005], dp[5005][5005], b[5005], tax[5005], ni[5005];

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (LL i = 1; i <= n; ++i) ni[i] = ksm(i, MO - 2);
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), ++tax[a[i]];

        LL ans = 0;
        tax[0] = 1;

        for (LL i = n; i >= 0; --i) {
            for (LL j = n; j >= 0; --j) if (tax[j]) {
                dp[i][j] = (ni[n - i] * b[j + 1] % MO + (tax[j] - 1) * ni[n - i] % MO) % MO;
                ans = (ans + dp[i][j]) % MO;
            }
            for (LL j = 1; j <= n; ++j) b[j] = dp[i][j] * tax[j] % MO;
            for (LL j = n; j >= 1; --j) b[j] = (b[j] + b[j + 1]) % MO;
        }

        cout << dp[0][0];

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}