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

· · 题解

有 m 种数，对于给定的一些前缀 L_1\le\dots\le L_n 随机 x\in[1,L_i] 重复两个形成序列 a，两个人选择元素，先手可以任意选，后手只会选开头，求先手选的元素之和期望。

思考确定序列后如何求解。考虑先手能选什么，容易发现条件为前 2i 个元素至多选 i 个。于是可以直接贪，用一个堆维护当前选的，如果超限了就弹。

直接拉过来做也太倒闭了，肯定要拆贡献，容易拆成 \ge x 的牌选了几张。发现此时令 a_i\rightarrow[a_i\ge x] 是没有问题的，于是可以直接把堆里面 1 的个数存进 dp 状态，这样可以做到 O(n^2m)。

接下来肯定是插值，就是 dp 里面每个值都是关于 x 的多项式，但是分成 O(n) 段每段跑 O(n) 次 O(n^2) dp 求点值就炸了。

发现一个前缀中 L 对 dp 无关，于是将 dp 转置倒着跑，然后每段取相应的后缀，这样就只需跑 O(n) 次 dp。

对于每段插值求函数的区间和即可，时间复杂度 O(n^3)。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
using namespace std;
namespace c0dE1ng{
constexpr int mod=1e9+7;
constexpr int N=505;
inline void inc(int &x,const int y){x+=y,x-=x>=mod?mod:0;}
inline void dec(int &x,const int y){x-=y,x+=x<0?mod:0;}
inline int ksm(int a,int b,const int p){a%=p;int r=1;while(b){if(b&1)r=r*1ll*a%p;a=a*1ll*a%p,b>>=1;}return r%p;}
inline int inv(const int x){return ksm(x,mod-2,mod);}
int n,m,a[N],f[N][N],F[N][N],y[N];
inline int Lag(int x){
    int res=0;rep(i,1,n+2){
        int p=1,q=1;rep(j,1,n+2)if(i!=j)p=p*1ll*(x-j+mod)%mod,q=q*1ll*(i-j+mod)%mod;
        inc(res,p*1ll*inv(q)%mod*y[i]%mod);
    }return res;
}
void main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;rep(i,1,n)cin>>a[i],a[i]+=a[i-1];
    rep(x,1,n+2){
        rep(i,0,n)rep(j,0,n)f[i][j]=0;rep(j,0,n)f[n][j]=j;
        per(i,n,1){
            const int p=(a[i]-x+mod+1)*1ll*inv(a[i])%mod;
            rep(j,0,n)inc(f[i-1][j],f[i][min(j+2,i)]*1ll*p%mod);
            rep(j,0,n)inc(f[i-1][j],f[i][j]*1ll*(1+mod-p)%mod);
        }rep(i,0,n)F[x][i]=f[i][0];
    }
    int ans=0;rep(i,1,n){
        rep(x,1,n+2)y[x]=F[x][i-1],inc(y[x],y[x-1]);
        inc(ans,Lag(a[i])),dec(ans,Lag(a[i-1]));
    }
    cout<<ans<<'\n';
}
}
int main(){
    auto _Tbe=TIME;
    c0dE1ng::main();
    auto _Ted=TIME;
    cerr<<"\nTIME:"<<_Ted-_Tbe<<"ms\n";
    return 0;
}
/*
ulimit -s 1048576
g++ -O2 -std=c++14 -static A.cpp -o %;size %;./% < A.in > A.out
*/

:::