题解：CF1156F Card Bag

zhanjinghan · 2026-10-22 19:56:09 · 题解

题意

有 n 个卡片，每次抽一张（不放回），若大于上一张则继续，等于上一张则胜利，小于上一张则失败；牌抽完后也算失败。

题解

设 cnt_i 为 i 的出现次数，dp_{i,j} 为前 i 个中抽出 j 个（包含第 i 个）的概率，则：

我们可以用前缀和优化。

设 sum_{i,j}=\sum\limits_{k=0}^{i}{dp_{k,j}}，则 dp_{i,j}=\frac{cnt_{a_i}}{n-j+1} \times sum_{i-1,j-1}。

最后答案为 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}{dp_{i,j}\times \frac{cnt_{a_i}-1}{n-j}}。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3+5,mod = 998244353;
int n,m,a[N],cnt[N];
ll dp[N][N],inv[N],sum[N][N];
// 前i个中抽出j个（包含i）的概率
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    inv[1] = 1;
    for (int i = 2;i <= 5e3;++ i){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod; // 预处理乘法逆元
    }
    cin>>n;
    for (int i = 1;i <= n;++ i){
        cin>>a[i];
        cnt[a[i]] ++;
    }
    sort(a+1,a+n+1); // 从小到大，因为先大后小就输了
    m = unique(a+1,a+n+1) - a - 1; // 去重
    sum[0][0] = 1;
    ll ans = 0;
    for (int i = 1;i <= m;++ i){
        sum[i][0] = 1;
        for (int j = 1;j <= i;++ j){
            // dp[i][j] = sum[i - 1][j - 1] * cnt[a[i]] / (n - j + 1)
            dp[i][j] = sum[i - 1][j - 1] * cnt[a[i]] % mod * inv[n - j + 1] % mod;
            sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod;
            // ans += dp[i][j] * (cnt[a[i]] - 1) / (n - j)
            ans = (ans + dp[i][j] * (cnt[a[i]] - 1) % mod * inv[n - j] % mod) % mod;
        }
    }
    cout<<ans;
    return 0;
}