题解：P15878 [ICPC 2026 NAC] Draw Your Deck

Aux_sky · 2026-10-19 20:33:49 · 题解

怎么不让直接计数，太可恶了。

首先由于洗牌随机所以策略就是能取就取，题意转化为随机一个排列问一直取能取完所有牌的概率。

考虑纯暴力怎么做，设 f_{i,j,k,l} 表示当前还剩 i 个 0，j 个 1，k 个 2，l 个 3 的获胜概率。

还能再取的牌数为 D=1+(a_1-j)+2(a_2-k)+3(a_3-l)-(a_0-i)-(a_1-j)-(a_2-k)-(a_3-l)。

化简得 D=1+(a_2-k)+2(a_3-l)-(a_0-i)。

• 若 i=0,j=0,k=0,l=0 则我们取完了所有牌，f_{i,j,k,l}=1。
• 若 D\le 0 则我们无法继续取牌，f_{i,j,k,l}=0。
• 否则我们有 \frac{i}{i+j+k+l} 的概率选到 0，\frac{j}{i+j+k+l} 的概率选到 1，以此类推。\displaystyle f_{i,j,k,l}=\frac{if_{i-1,j,k,l}+jf_{i,j-1,k,l}+kf_{i,j,k-1,l}+lf_{i,j,k,l-1}}{i+j+k+l}

直接这么做是 \mathcal O(n^4) 的，我们发现已经离正解很近了，猜测正解就是暴力。

我们发现抽到一个 1 对 D 是没有影响的，我们不妨在状态里删掉 1，在最后再考虑 1 的影响，于是 DP 可以做到 \mathcal O(n^3)，带 \frac 1 {27} 的常数，滚动数组是完全可以过的。

设 S=1-a_0+a_2+2a_3，即删完所有非 1 的牌之后还能再取几张牌。

1. 若 S>0，则 1 的位置是无所谓的，ans 不变。
2. 若 S=0，则取完所有非 1 的之后就不能再有 1 了，也就是排列的最后一个不能是 1，\displaystyle ans=\frac{(n-a_1)ans}{n}。
3. 若 S<0，显然无论如何都是取不完所有牌的，ans=0。

::::success[Code]

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<=k;++i)scanf("%d",&a[i]);
    for(int i=0;i<=a[0];++i){
        for(int j=0;j<=a[2];++j)
            for(int k=0;k<=a[3];++k)g[j][k]=f[j][k],f[j][k]=0;
        for(int j=0;j<=a[2];++j)
            for(int k=0;k<=a[3];++k){
                if(!i&&!j&&!k){f[j][k]=1;continue;}
                if((a[3]-k)*2+(a[2]-j)-(a[0]-i)+1<=0){f[j][k]=0;continue;}
                int r=i+j+k;
                if(i)f[j][k]+=g[j][k]*i/r;
                if(j)f[j][k]+=f[j-1][k]*j/r;
                if(k)f[j][k]+=f[j][k-1]*k/r;
            }
    }
    ans=f[a[2]][a[3]];
    int S=a[2]+a[3]*2-a[0]+1;
    if(S==0)ans=ans*(n-a[1])/n;
    else if(S<0)ans=0;
    printf("%.10lf",ans);
    return 0;
}

::::