题解：P12251 [科大国创杯初中组 2025] 抽卡【暂无数据】

· · 题解

\text{Solution}

先分析一下如果牌堆确定了应该怎么做最优：

倒着处理牌堆，每次将两张卡牌的价值加入堆中并再弹出堆中最大值，n 次之后牌取完，所有牌的值之和减堆中剩的 n 个数之和就是答案。

52 分 \mathcal{O}(n^2m) 做法

先分析一下 52 分 \mathcal{O}(n^2m) 怎么写：

所有牌的值之和很好求。

对于一种方案堆中剩的所有值之和我们考虑拆贡献：

ans=\sum_{k=1}^{n}v_k=\sum_{k=1}^{n}\sum_{i=1}^{m}[v_k\ge i]=\sum_{i=1}^{m}\sum_{k=1}^{n}[v_k\ge i] 所以我们考虑枚举 $i$，求： $$S=\sum_{j=1}^{n}[v_j\ge i]$$ 此时只分两种权值 $1/0$，即 $[v_j\ge i]$。 设 $b_i=\sum_{j=1}^{i}a_i$，若当前枚举的数为 $w$，则第 $i$ 次随机选择的卡牌值为 $0$ 的方案数为 $\min(w-1,b_i)$，为 $1$ 的方案数为 $\max(0,b_i-w+1)$。 我们从后往前 dp，$f_{i,j}$ 表示处理好了第 $i$ 到 $n$ 次选择堆中有个 $j$ 数值为 $1$。 转移即： $$\large{f_{i,j}=f_{i+1,j+1}\times \min(w-1,b_i) +f_{i+1,j-1}\times \max(0,b_i-w+1)}$$ $$\large{S=\sum_{j=1}^{n}[v_j\ge i]=\sum_{i=1}^{n} f_{1,i} \times i}$$ 至此 $52$ 分结束。 ## $100$ 分 $\mathcal{O}(n^3)

比较明显 f_i 数组维护的是一个关于 w 的多项式，因为 b_i 递增我们可以发现对于 b_i\ge w 的所有 w,f_i 维护的多项式系数相同。

现在如果我们得到了 f_i 的系数，并且 b_{i-1}<w。那么 f_{i-1,j}=f_{i,j+1}\times b_{i-1} +f_{i,j-1}\times 0=f_{i,j+1}\times b_{i-1}。

所以 f_{1,j}=f_{i,j+i-1}\times \prod_{k=1}^{i-1}b_k。

因此从后往前暴力算 f_{i} 的系数，然后就可以统计 b_{i-1}<w\le b_i 的所有 w 的答案。

设 f_{i,j} 为 f_i 第 j 项的系数。

即:

\sum_{w=b_{i-1}+1}^{b_i} \sum_{j=1}^{n} f_{i,j+i-1} \times \prod_{k=1}^{i-1}b_k \times w^{j+i-1}=\prod_{k=1}^{i-1}b_k \times \sum_{j=1}^{n} f_{i,j+i-1} \times \sum_{w=b_{i-1}+1}^{b_i}w^{j+i-1}

最后我们用斯特林数或拉插求自然数幂和即可。

斯特林数求法：

\sum_{i=1}^{n} i^k=\sum_{i=1}^{n}\sum_{j=1}^{k}\begin{Bmatrix} k \\ j\end{Bmatrix}\times j! \times {i \choose j}=\sum_{j=1}^{k}\begin{Bmatrix} k \\ j\end{Bmatrix}\times j! \times \sum_{i=1}^{n}{i \choose j}=\sum_{j=1}^{k}\begin{Bmatrix} k \\ j\end{Bmatrix}\times j! \times {n+1 \choose j+1}

数据出来再放代码。

#include<bits/stdc++.h>
using namespace std;
const int N=505,mod=1e9+7;
#define vr vector<int>
int n,m,a[N],s=1,ans,sss,mi[N],inv[N],st[N][N],ss[N][N];vr f[N][N];
inline int pw(int x,int y) {
  int z=1;
  for(;y;y>>=1,x=x*1ll*x%mod) if(y&1) z=z*1ll*x%mod;
  return z;
}
inline void ad(int &u,int v) {u+=v;(u>=mod&&(u-=mod));}
inline vr add2(vr x,vr y) {
  vr z(max(x.size(),y.size()),0);
  for(int i=0;i<x.size();++i) ad(z[i],x[i]);
  for(int i=0;i<y.size();++i) ad(z[i],y[i]);
  return z;
}
inline vr mul(vr x,vr y) {
  vr z(x.size()+y.size()-1,0);
  for(int i=0;i<x.size();++i) for(int j=0;j<y.size();++j) ad(z[i+j],x[i]*1ll*y[j]%mod);
  return z;
}
inline int calc(int x) {return x*1ll*(x+1)/2ll%mod;}
vr tp;
inline vr make(int x,int y) {vr().swap(tp);tp.emplace_back(y);tp.emplace_back(x);return tp;}
inline vr make2(int x) {vr().swap(tp);tp.emplace_back(x);return tp;}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) scanf("%d",a+i),a[i]+=a[i-1],s=s*1ll*a[i]%mod;sss=s;
  for(int i=1;i*2<=n;++i) swap(a[i],a[n+1-i]);
  for(int i=1;i<=n;++i) ans=(ans+calc(a[i])*1ll*s%mod*pw(a[i],mod-2))%mod;
  st[0][0]=1;ans=ans*2%mod;
  for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) st[i][j]=(j*1ll*st[i-1][j]+st[i-1][j-1])%mod;
  for(int i=1;i<=n+2;++i) inv[i]=pw(i,mod-2);
  for(int i=1;i<=n;++i) {
    mi[0]=1;
    for(int j=1;j<=n+1;++j) mi[j]=mi[j-1]*1ll*(a[i]+2-j)%mod;
    for(int j=0;j<=n;++j) for(int k=0;k<=j;++k) ss[i][j]=(ss[i][j]+st[j][k]*1ll*inv[k+1]%mod*mi[k+1])%mod;
  }
  f[0][0].emplace_back(1);ss[n+1][0]=1;
  for(int i=1;i<=n;++i) {
    for(int j=0;j<i;++j) {
      f[i][j+1]=add2(f[i][j+1],mul(make(mod-1,a[i]+1),f[i-1][j]));
      f[i][max(j-1,0)]=add2(f[i][max(j-1,0)],mul(make(1,mod-1),f[i-1][j]));
    }
    vr g;g.clear();
    for(int j=n-i+1;j<=n;++j) g=add2(g,mul(make2(j-n+i),f[i][j]));
    s=s*1ll*pw(a[i],mod-2)%mod;
    for(int j=0;j<(int)g.size();++j) ans=(ans-g[j]*1ll*s%mod*(ss[i][j]-ss[i+1][j]))%mod;
  }
  if(ans<0) ans+=mod;ans=ans*1ll*pw(sss,mod-2)%mod;
  printf("%d\n",ans);
  return 0;
}