P5299 [PKUWC2018]Slay the Spire

    • 43通过
    • 89提交
  • 题目提供者 memset0 管理员
  • 评测方式 云端评测
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    九条可怜在玩一个很好玩的策略游戏: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$

    输入输出格式

    输入格式:

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

    接下来对于每组数据:

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

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    19
    253973805

    说明

    样例解释

    例如九条可怜抽到了攻击牌 $\{1,2\}$ 和强化牌 $\{3\}$,那最优策略是先用掉强化牌 $3$,此时攻击牌的数值变成 $\{3,6\}$,然后打出 $6$。

    数据范围

    对于所有数据,有 $1\leq k\leq m\leq 2n\leq 3\times 10^3$,且$1\leq w_i\leq 10^8$。

    保证强化牌上的数字都大于 1

    以下 $(\sum 2n)$ 表示对于输入中所有数据的$2n$的和。

    对于 $10\%$ 的数据,有 $1\leq \sum 2n\leq 10$

    对于 $20\%$ 的数据,有 $1\leq \sum 2n\leq 100$

    对于 $30\%$ 的数据,有 $1\leq \sum 2n\leq 500$

    另有 $20\%$ 的数据,满足所有攻击牌的数值相同。

    另有 $20\%$ 的数据,满足 $m=k$。

    对于 $100\%$ 的数据,有 $1\leq \sum 2n\leq 30000$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。