LOJ#2538. 「PKUWC2018」Slay the Spire-布布扣-bubuko.com

Description

九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有2n张牌，每张牌上都写着一个

数字wi，一共有两种类型的牌，每种类型各n张：1.攻击牌：打出后对对方造成等于牌上的数字的伤害。2.强化牌

：打出后，假设该强化牌上的数字为x，则其他剩下的攻击牌的数字都会乘上x。保证强化牌上的数字都大于1。现

在九条可怜会等概率随机从卡组中抽出m张牌，由于费用限制，九条可怜最多打出k张牌，假设九条可怜永远都会采

取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为y，你只需要输出

（2n）!*y / (m!*(2n-m)!) Mod 998244353

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

接下来对于每组数据：

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

第二行n个正整数wi，表示每张强化牌上的数值。

第三行n个正整数wi，表示每张攻击牌上的数值。

1<=k<=m<=2n<=3e3

1<=wi<=1e8

Σ2n <= 3e4

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

2
2 3 2
2 3
1 2
10 16 14
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10

19
253973805

可以发现题目要求的期望是假的，乘上的那个相当于一个总方案数

也就是说只要求出所有抽m张牌的产生的总和即可

再进一步分析题目，发现强化卡>=1的性质使得必定是先尽量用强化卡

设强化卡的数量为i

当$i<k$时，有多少用多少，接下来再用最大的$k-i$张攻击卡

当$i>k$时，用$k-1$张强化卡，再用一张最大的攻击卡