题目链接：Codeforces 1156F

你有一个装有 $n$ 张卡片的袋子，第 $i$ 张卡片上的数字为 $a_i$。

接下来你要玩一个卡片游戏。每一回合，你会随机选择选择袋子里的一张卡片（所有留在袋子里的卡片都是等概率选择的）。从第二回合起，每当你拿出一张卡片（将上面的数字记为 $x$），你都会和上一回合的卡片（将上面的数字记为 $y$）比较：

• 如果 $x < y$，你将会输掉游戏，游戏结束。
• 如果 $x = y$，你将会赢得游戏，游戏结束。
• 如果 $x > y$，游戏继续。

如果袋子里没有卡片了，那么你也将输掉游戏。注意：你取出来的卡片不会重新放回袋子里。

请你求出赢得游戏的概率，答案对 $998244353$ 取模。

数据范围：$2 \le n \le 5000$，$1 \le a_i \le n$。

Solution

分析题意可得，如果要赢得游戏，那么取出的卡片序列 $x_1, x_2, \dots, x_k$ 一定满足 $x_1 < x_2 < \dots < x_{n - 1}, x_{n - 1} = x_n$。

前面一部分考虑动态规划。设 $f(i, j)$ 表示已经进行了 $i$ 个回合，最后一次取出的卡片为 $j$，那么我们枚举上一次的卡片 $k$，则有：

$$ f(i, j) = \sum_{k = 1} ^ {j - 1} f(i - 1, k) \cdot \frac{cnt(k)}{n - i + 1} $$

其中 $cnt(i)$ 表示数字为 $i$ 的卡片的数量。转移可以前缀和优化，复杂度为 $\mathcal O(n ^ 2)$。

最后考虑 $x_{n - 1} = x_n$ 的部分，我们枚举 $i, j$，如果 $cnt(j) > 1$，那么意味着还可以取到数字为 $j$ 的卡片，对答案有 $f(i, j) \cdot \frac{cnt(j) - 1}{n - i}$ 的贡献。

时间复杂度：$\mathcal O(n ^ 2)$。

Code

#include <cstdio>

const int N = 5e3 + 5;
const int P = 998244353;

int n, inv[N], cnt[N], f[N][N];

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void init(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
    }
    init(n);
    for (int i = 1; i <= n; i++) {
        f[1][i] = 1LL * cnt[i] * inv[n] % P;
    }
    for (int i = 2; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            f[i][j] = 1LL * cnt[j] * sum % P;
            add(sum, 1LL * f[i - 1][j] * inv[n - (i - 1)] % P);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (cnt[j] > 1) add(ans, 1LL * f[i][j] * (cnt[j] - 1) % P * inv[n - i] % P);
        }
    }
    printf("%d\n", ans);
    return 0;
}