BZOJ 5467 Slay the Spire
2024-10-19 03:30:18
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;}
最新文章
- 一个神奇的POS -扫描 现场销售 开单打印票据 安卓物联网POS机 手持开单终端机 省时省力 高效准确!!
- MS - 1 - 把二元查找树转变成排序的双向链表
- UOJ265 【NOIP2016】愤怒的小鸟
- 深入理解Java虚拟机之读书笔记二 垃圾收集器
- MySql变量,
- C# WPF 显示图片和视频显示 EmuguCv、AForge.Net测试(续)
- EDIUS和VEGAS哪个更好用
- caffe源码阅读(2)-Layer
- Android开发之模板模式初探
- 左右mysql事务提交
- 共享Visio和project的下载链接
- 能够玩转BKY皮肤的 geek,有一半最后都成为了前端大师
- centos7安装xfce桌面
- 深入理解Java中的多态
- 语义SLAM的数据关联和语义定位(三)
- Entity framework 增加默认执行时间
- Spring Boot 8080端口被占用抛出异常
- Maven中使用Jetty容器
- CSS Spritec下载,精灵图,雪碧图,初探之原理、使用
- docker学习记录1