#2538. 「PKUWC2018」Slay the Spire

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

九条可怜在玩一个很好玩的策略游戏: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 行,每行一个非负整数表示每组数据的答案。

样例

样例输入

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

样例解释

例如九条可怜抽到了攻击牌 \{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