P12251 [科大国创杯初中组 2025] 抽卡 题解

huangleyi0129 · 2025-05-01 23:03:26 · 题解

场外 VP，小朋友太惨了。

O(n^2m) 做法

非常经典地，将 \ge x 的数视为 1，其余视为 0，这样就将贡献拆掉，问题简化。

与马队和 asdfz 的诸位大佬不同的是，我的朴素 DP 是正着做的（这样似乎更易理解和记答案？）。

设 f_{i,j} 表示前 2i 个数中合法选出 j 个 1 的概率，p_i=\sum_{k=1}^{i} a_k。

则 f_{i,j}=f_{i-1,j-2}\cdot (1-\frac{x-1}{p_i}) +f_{i-1,j}\cdot \frac{x-1}{p_i} ，其中 j\le i,p_i\ge x。

易知对答案的贡献为 \sum j f_{n,j}。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const long long mod=1000000007;
long long f[N][2],inv,ans;
int n,m,s,a[N],p[N];
long long qpow(long long x,int y)
{
    long long z=1;
    while(y)
    {
        if(y&1)
            z=z*x%mod;
        x=x*x%mod,y>>=1;
    }
    return z;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int cur;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i],p[i]=a[i]+p[i-1];
    for(int t=1;t<=n;s+=a[t],++t)
    {
        for(int x=s+1;x<=s+a[t];++x)
        {
            memset(f,0,sizeof f),f[0][0]=1,cur=1;
            for(int i=t;i<=n;++i,cur^=1)
            {
                inv=(p[i]-x+1)*qpow(p[i],mod-2)%mod;
                for(int j=0;j<=i;++j)
                {
                    f[j][cur]=f[j][!cur]*(1-inv)%mod;
                    if(j>=2)
                        f[j][cur]=(f[j][cur]+f[j-2][!cur]*inv)%mod;
                }
                f[i][cur]=(f[i][cur]+f[i-1][!cur]*inv)%mod;
            }
            for(int j=1;j<=n;++j)
                ans=(ans+j*f[j][!cur])%mod;
        }
    }
    cout<<(ans+mod)%mod;
    return 0;
}

O(n^3) 做法

上述做法大约只能用拉插优化到 O(n^4)，原因在于未能有效利用之前的信息。

要作一个转化，合法相当于后 2i 个数至少取 i 个，即在每个 2j+1 处取局部最优值，再拆一下期望，具体见 Purslane 的题解。

下面就与他们的 DP 式子一样了，处理时我是记录下降幂的系数，使用一些有限微积分的技巧求和，即：