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

· · 题解

看完题目，很容易想到记录现在抽了多少张牌面为 0/1/2/3 的牌，复杂度为 O((\dfrac{n}{4})^4)， 离过掉这题还有一点距离。

接着，注意力惊人的你发现，牌面为 1 的牌非常没用，你取了它消耗 1 张你能取的牌，然后又能多取 1 张牌，合计你取了它和没取没有什么区别。

于是你信誓旦旦地把 DP 改成只记录 0/2/3 的牌，复杂度为 O((\dfrac{n}{3})^3)，这下能过了。

等等，怎么挂了？我们发现实现还有一点细节，原本 DP 的时候，f_{a,b,c,d} 这个状态可以取到，当且仅当 (b+2c+3d\geq a+b+c+d)\lor((b+2c+3d=n-1)\land(a+b+c+d=n))。

而在缺少 b 这一维后，第二个条件变得不好判断，所以我们考虑在 DP 外把它判了，第二个条件指的是刚刚好把最后 1 张牌取完，不能再多取了，这意味着我们把牌面为 1 插入到牌堆中，不能插到末尾，也就是要给整体概率乘上 \dfrac{n-a_0}{n}，也就是不插末尾的概率。（注意不要乱乘，只有 a_2+2a_3-a_0=-1 时乘。）

码风很丑，见谅。

#include<bits/stdc++.h>
using namespace std;
int n,K,c[5];
double f[2000005];
int w(int x,int y,int z){return x*(c[2]+1)*(c[3]+1)+y*(c[3]+1)+z;}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>K;
    for(int i=0;i<=K;i++)cin>>c[i];
    f[w(0,0,0)]=1;
    if(c[2]+c[3]*2-c[0]==-1)f[w(0,0,0)]=double(n-c[1])/n;
    for(int i=0;i<=c[0];i++)
    {
        for(int j=0;j<=c[2];j++)
        {
            for(int k=i==0&&j==0,h;k<=c[3];k++)
            {
                h=i+j+k;
                f[w(i&1,j,k)]=0;
                if(j*2+k*3>=h||j*2+k*3==h-1&&i+j+k==c[0]+c[2]+c[3])
                {
                    if(i)f[w(i&1,j,k)]+=f[w(i&1^1,j,k)]*i/h;
                    if(j)f[w(i&1,j,k)]+=f[w(i&1,j-1,k)]*j/h;
                    if(k)f[w(i&1,j,k)]+=f[w(i&1,j,k-1)]*k/h;
                }
            }
        }
    }
    cout<<fixed<<setprecision(10)<<f[w(c[0]&1,c[2],c[3])];
    return 0;
}