Siyuan

「Codeforces 1156F」Card Bag
「Codeforces 1156F」Card Bag
扫描右侧二维码阅读全文
20
2019/05

「Codeforces 1156F」Card Bag

题目链接: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;
}

发表评论