BZOJ 5467 Slay the Spire

浅浅的花香味﹌ 2021-12-23 03:39 128阅读 0赞

### BZOJ 5467 Slay the Spire ###

*  我的概率基础也太差了.jpg

大概就是这样，因为强化牌至少翻倍，所以打出的牌必定是全部的强化牌或者$k-1$个强化牌，然后剩余的机会打出最大的几个攻击牌。

我们对于强化牌和攻击牌分别做，并且显然，排序并不会影响答案。

$f\[i\]\[j\]$表示前$i$张牌，取到$j$张，第$i$张必定取的最大强化值之积，$g\[i\]\[j\]$表示前$i$张攻击牌，取到$j$张，第$i$张必定取的最大伤害和。（一般来说，应该先考虑第$i$张不必需取的最大值，但是由于那样设计状态并不能优化成$n^2$，所以只能选择第$i$张必须选的答案）

$f\[i\]\[j\]=a\_i\\times \\sum\\limits\_\{k=j-1\}^\{i-1\} f\[k\]\[j-1\]$

$g\[i\]\[j\]=C(i-1,j-1)\\times b\_i+\\sum\\limits\_\{k=j-1\}^\{i-1\} g\[k\]\[j-1\]$

然后剩下的就是如何计算答案了。

那么很显然，我们要求的是前$n$张排中，选择$j$个，第$n$个**不必需**选择的答案。

因此设$F(i,j)$表示摸到$i$张，选择$j$个的最大强化之积。那么很显然，$F(i,j)=\\sum\\limits\_\{k=i\}^nf\[k\]\[j\]\\times C(n-k,i-j)$

同时设$G(i,j)$表示摸到$i$张，选择$j$个的最大伤害之和。那么很显然，$G(i,j)=\\sum\\limits\_\{k=i\}^n g\[k\]\[j\]\\times C(n-k,i-j)$

同样，根据我们最初得到的结论，$ans=\\sum\\limits\_\{i=0\}^\{k-1\}F(i,i)\\times G(m-i,k-i)+\\sum\\limits\_\{i=k\}^m F(i,k-1)\\times G(m-i,1)$

#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <queue> #include <iostream> #include <bitset> using namespace std; #define N 3005 #define ll long long #define mod 998244353 int f[N][N],g[N][N],n,k,a[N],b[N],m,sum[N],C[N][N]; void init() { for(int i=0;i<=3000;i++) { C[i][0]=1; for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } } int F(int x,int y) { if(x<y)return 0;if(!y)return C[n][x];int ret=0; for(int i=x-y+1;i<=n-y+1;i++)ret=(ret+(ll)f[y][i]*C[i-1][x-y])%mod; return ret; } int G(int x,int y) { if(x<y)return 0;int ret=0; for(int i=x-y+1;i<=n-y+1;i++)ret=(ret+(ll)g[y][i]*C[i-1][x-y])%mod; return ret; } void solve() { scanf("%d%d%d",&n,&m,&k); // memset(f,0,sizeof(f));memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) f[i][j]=g[i][j]=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); sort(a+1,a+n+1);sort(b+1,b+n+1); for(int i=1;i<=n;i++)f[1][i]=a[i],sum[i]=(sum[i-1]+a[i])%mod; for(int i=2;i<=n;i++) { for(int j=1;j<=n-i+1;j++)f[i][j]=(ll)a[j]*(sum[n]-sum[j]+mod)%mod; for(int j=1;j<=n-i+1;j++)sum[j]=(sum[j-1]+f[i][j])%mod; for(int j=n-i+2;j<=n;j++)sum[j]=sum[j-1]; } for(int i=1;i<=n;i++)g[1][i]=b[i],sum[i]=(sum[i-1]+b[i])%mod; for(int i=2;i<=n;i++) { for(int j=1;j<=n-i+1;j++)g[i][j]=((ll)b[j]*C[n-j][i-1]+sum[n]-sum[j]+mod)%mod; for(int j=1;j<=n-i+1;j++)sum[j]=(sum[j-1]+g[i][j])%mod; for(int j=n-i+2;j<=n;j++)sum[j]=sum[j-1]; } int ans=0; for(int i=0;i<m;i++) { if(i<k)ans=(ans+(ll)F(i,i)*G(m-i,k-i))%mod; else ans=(ans+(ll)F(i,k-1)*G(m-i,1))%mod; } printf("%d\n",ans); } int main(){init();int T;scanf("%d",&T);while(T--)solve();return 0;}

转载于:https://www.cnblogs.com/Winniechen/p/10623371.html