题解 CF1156F 【Card Bag】

· · 题解

题目传送门。

题意简述：有 n 张卡牌，每张卡牌有数字 a_1,a_2,\cdots,a_n。现在随机抽取卡牌，不放回，设本次抽到的卡牌为 x，上次抽到的卡牌为 y，若 x=y 则游戏胜利；若 x<y 则输掉游戏；若 x>y 则游戏继续。求获胜概率。

下文认为 a_i 与 n 同阶。

不难发现我们只关心卡牌上的数字，所以开个桶维护每个数出现了几次。又因为只能从小往大抽，即无后效性，所以考虑 DP。

设 f_{i,j} 为 共抽了 j 次，每个数最多抽到一次，最后一次抽到数字 i 的概率。

首先考虑如何转移：我们设数字 i 共有 sz_i 个，那么不难列出转移方程

f_{i,j}=\sum_{k=0}^{i-1}f_{k,j-1}\times \frac{sz_i}{n-j+1}

表示 在 [1,i-1] 中抽了 j-1 个数 的概率乘上 抽到数字 i 的概率。这样转移的时间复杂度为 \mathcal{O}(n^3)，无法接受。

如果设 s_{i,j} 为 在 i 中抽了 j 个数 的概率，则有

s_{i,j}=\sum_{k=1}^{i}f_{i,j}

则转移方程可变形为

f_{i,j}=\frac{s_{i-1,j-1}sz_i}{n-j+1}

预处理逆元做到时间复杂度 \mathcal{O}(n^2)，可以接受。

这实际上就是具有实际意义的前缀和优化。

最后使用滚动数组可以将空间优化到 \mathcal{O}(n)。

需要注意初始值 f_{0,0}=1。

const int N=5e3+5;
ll n,ans,sz[N],f[2][N],s[2][N];
int main(){
    init(),cin>>n,s[0][0]=s[1][0]=1;
    for(int i=1,a;i<=n;i++)cin>>a,sz[a]++;
    for(int i=1,p=1;i<=n;i++,p^=1){
        for(int j=1;j<=i;j++){
            f[p][j]=s[p^1][j-1]*sz[i]%mod*iv[n-j+1]%mod;
            ans=(ans+s[p^1][j-1]*sz[i]*(sz[i]-1)%mod*iv[n-j+1]%mod*iv[n-j])%mod;
            s[p][j]=(s[p^1][j]+f[p][j])%mod;
        }
    } cout<<ans<<endl;
    return 0;
}