【PKUWC2018】Slay the Spire

2019/01/18 19:38
阅读数 5

Description

<font size="3">

九条可怜在玩一个很好玩的策略游戏:Slay the Spire,一开始九条可怜的卡组里有 $2n$ 张牌,每张牌上都写着一个数字$w_i$,一共有两种类型的牌,每种类型各 $n$ 张:

  1. 攻击牌:打出后对对方造成等于牌上的数字的伤害。

  2. 强化牌:打出后,假设该强化牌上的数字为 $x$,则其他剩下的攻击牌的数字都会乘上 $x$。保证强化牌上的数字都大于 1。

现在九条可怜会等概率随机从卡组中抽出 $m$ 张牌,由于费用限制,九条可怜最多打出 $k$ 张牌,假设九条可怜永远都会采取能造成最多伤害的策略,求她期望造成多少伤害。

假设答案为 $\text{ans}$,你只需要输出

$$ \left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353 $$

即可

其中 $x!$ 表示 $\prod_{i=1}^{x}i$,特别地,$0!=1$

</font>

Input

<font size="3">

第一行一个正整数 $T$ 表示数据组数

接下来对于每组数据:

第一行三个正整数 $n,m,k$

第二行 $n$ 个正整数 $w_i$,表示每张强化牌上的数值。

第三行 $n$ 个正整数 $w_i$,表示每张攻击牌上的数值。

</font>

Output

<font size="3">

输出 $T$ 行,每行一个非负整数表示每组数据的答案。

</font>

Solution

<font size=“3”>

据说是去年的<del>签到题</del>啊。。<del>九条可怜竟然会出签到题!</font>

但是这道题我还是想了很久。。

首先我们要考虑最优的出牌策略。

有加强肯定先加强,留着加强牌不出先出攻击牌肯定是不优的。。因为加强牌的数值都大于$1$

那么我们出牌肯定是从大到小出加强牌,当出完或者出了$k-1$张后。考虑从大到小出攻击牌。这样就能使伤害最多

考虑DP

因为每种牌都是从大到小出的。。不妨我们先将每种牌按从大到小的顺序排序

令$G_{i,j}$表示前$i$张加强牌,选了$j$张,第$i$张牌必须选的不同方案乘积和,显然有

$$G_{i,j}=\sum_{k=j-1}^{i-1} {G_{k,j-1} * w_i}$$

同理,有$F_{i,j}$表示前$i$张攻击牌,选了$j$张,第$i$张牌必须选的不同方案的攻击力和,有

$$F_{i,j}=\sum_{k=j-1}^{i-1} {F_{k,j-1}+C_{k}^{j-1} * w_i}$$

用前缀和优化后复杂度为$O(n^2)$

考虑统计答案

我们枚举在$m$张牌中有几张加强牌,设加强牌数量为$t$

若$t \leq k-1$,意味着我们可以打完所有的加强牌再打攻击牌。

若$k \leq t$,则我们只能从大到小出$k-1$张加强牌后打一张权值最大的攻击牌

配合组合数计算即可

</font>

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3010,Mod=998244353;
int F[N][N],G[N][N],add_sum[N],pro_sum[N],mul_sum[N],J[N],R[N];
int T,n,m,k,w[N],atk[N],ans;
int read()
{
	int ans=0;char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
	return ans;
}
int C(int x,int y)
{ 
	return (x>=y?1LL*J[x]*R[y]%Mod*R[x-y]%Mod:0);
}
int fpow(int a,int k)
{
	int ans=1;
	while (k)
	{
		if (k&1) ans=1LL*ans*a%Mod;
		a=1LL*a*a%Mod;
		k>>=1;
	}
	return ans;
}
bool cmp(int a,int b)
{
	return a>b;
}
void init()
{
	ans=0;
	memset(F,0,sizeof(F));
	memset(G,0,sizeof(G));
	memset(add_sum,0,sizeof(add_sum));
	memset(pro_sum,0,sizeof(pro_sum));
	memset(mul_sum,0,sizeof(mul_sum));
}
int main()
{
	J[0]=1;
	for (int i=1;i<=3000;i++) J[i]=1LL*J[i-1]*i%Mod;
	for (int i=0;i<=3000;i++) R[i]=fpow(J[i],Mod-2);
	T=read();
	while (T--)
	{
		init();
		n=read(),m=read(),k=read();
		for (int i=1;i<=n;i++) w[i]=read();
		for (int i=1;i<=n;i++) atk[i]=read();
		sort(w+1,w+n+1,cmp);
		sort(atk+1,atk+n+1,cmp);
		mul_sum[0]=1;
		G[0][0]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=min(i,k-1);j++)
				G[i][j]=(G[i][j]+1LL*mul_sum[j-1]*w[i]%Mod)%Mod;
			for (int j=1;j<=min(i,k-1);j++)
				mul_sum[j]=(mul_sum[j]+G[i][j])%Mod;
		}
		pro_sum[0]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=min(i,k);j++)
				F[i][j]=((F[i][j]+1LL*pro_sum[j-1]*atk[i]%Mod)%Mod+add_sum[j-1])%Mod;
			for (int j=1;j<=min(i,k);j++)
			{
				add_sum[j]=(add_sum[j]+F[i][j])%Mod;
				pro_sum[j]=(pro_sum[j]+C(i-1,j-1))%Mod;
			}
		}
		for (int i=0;i<=min(n,m-1);i++)
		{
			if (m-i>n) continue;
			if (i<k)
			{
				int num=0,res=k-i;
				for (int j=i;j<=n;j++) num=(num+G[j][i])%Mod;
				for (int j=res;j<=n;j++) 
					ans=(ans+1LL*num*F[j][res]%Mod*C(n-j,m-k)%Mod)%Mod;
                                        //因为要保证res张攻击牌只能在前j张产生。所以要使得m-k张攻击牌的权值小于前j张
			}
			else
			{
				int num=0;
				for (int j=k-1;j<=n;j++) num=(num+1LL*G[j][k-1]*C(n-j,i-(k-1))%Mod)%Mod;
				for (int j=1;j<=n;j++)
					ans=(ans+1LL*num*F[j][1]%Mod*C(n-j,m-i-1)%Mod)%Mod;//同理
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部