专栏文章

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

zzxc_a
P12251题解参与者 15已保存评论 17

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
17 条
当前快照
1 份
快照标识符
@mipjrdy5
此快照首次捕获于
2025/12/03 13:08
3 个月前
此快照最后确认于
2025/12/03 13:08
3 个月前
查看原文

Solution\text{Solution}

先分析一下如果牌堆确定了应该怎么做最优：
倒着处理牌堆，每次将两张卡牌的价值加入堆中并再弹出堆中最大值，nn 次之后牌取完，所有牌的值之和减堆中剩的 nn 个数之和就是答案。

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

先分析一下 5252 分 O(n2m)\mathcal{O}(n^2m) 怎么写：
所有牌的值之和很好求。
对于一种方案堆中剩的所有值之和我们考虑拆贡献：
ans=∑k=1nvk=∑k=1n∑i=1m[vk≥i]=∑i=1m∑k=1n[vk≥i]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]
vv 指的是堆中剩的 nn 个值。
所以我们考虑枚举 ii，求：
S=∑j=1n[vj≥i]S=\sum_{j=1}^{n}[v_j\ge i]
此时只分两种权值 1/01/0，即 [vj≥i][v_j\ge i]。
设 bi=∑j=1iaib_i=\sum_{j=1}^{i}a_i，若当前枚举的数为 ww，则第 ii 次随机选择的卡牌值为 00 的方案数为 min⁡(w−1,bi)\min(w-1,b_i)，为 11 的方案数为 max⁡(0,bi−w+1)\max(0,b_i-w+1)。
我们从后往前 dp，fi,jf_{i,j} 表示处理好了第 ii 到 nn 次选择堆中有个 jj 数值为 11。
转移即：
fi,j=fi+1,j+1×min⁡(w−1,bi)+fi+1,j−1×max⁡(0,bi−w+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)}
S=∑j=1n[vj≥i]=∑i=1nf1,i×i\large{S=\sum_{j=1}^{n}[v_j\ge i]=\sum_{i=1}^{n} f_{1,i} \times i}
至此 5252 分结束。

100100 分 O(n3)\mathcal{O}(n^3)

比较明显 fif_i 数组维护的是一个关于 ww 的多项式，因为 bib_i 递增我们可以发现对于 bi≥wb_i\ge w 的所有 w,fiw,f_i 维护的多项式系数相同。
现在如果我们得到了 fif_i 的系数，并且 bi−1<wb_{i-1}<w。那么 fi−1,j=fi,j+1×bi−1+fi,j−1×0=fi,j+1×bi−1f_{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}。
所以 f1,j=fi,j+i−1×∏k=1i−1bkf_{1,j}=f_{i,j+i-1}\times \prod_{k=1}^{i-1}b_k。
因此从后往前暴力算 fif_{i} 的系数，然后就可以统计 bi−1<w≤bib_{i-1}<w\le b_i 的所有 ww 的答案。
设 fi,jf_{i,j} 为 fif_i 第 jj 项的系数。
即:
∑w=bi−1+1bi∑j=1nfi,j+i−1×∏k=1i−1bk×wj+i−1=∏k=1i−1bk×∑j=1nfi,j+i−1×∑w=bi−1+1biwj+i−1\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}
最后我们用斯特林数或拉插求自然数幂和即可。
斯特林数求法：
∑i=1nik=∑i=1n∑j=1k{kj}×j!×(ij)=∑j=1k{kj}×j!×∑i=1n(ij)=∑j=1k{kj}×j!×(n+1j+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}
数据出来再放代码。
CPP
#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;
}

评论

共 17 条评论，欢迎与作者交流。

正在加载评论...