#2538. 「PKUWC2018」Slay the Spire

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

题目描述

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

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

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

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

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

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

即可

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

输入格式

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

接下来对于每组数据:

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

第二行 nn 个正整数 wiw_i,表示每张强化牌上的数值。

第三行 nn 个正整数 wiw_i,表示每张攻击牌上的数值。

输出格式

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

样例

样例输入

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}\{1,2\} 和强化牌 {3}\{3\},那最优策略是先用掉强化牌 33,此时攻击牌的数值变成 {3,6}\{3,6\},然后打出 66

数据范围与提示

对于所有数据,有 1km2n3×1031\leq k\leq m\leq 2n\leq 3\times 10^3,且1wi1081\leq w_i\leq 10^8

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

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

对于 10%10\% 的数据,有 12n101\leq \sum 2n\leq 10

对于 20%20\% 的数据,有 12n1001\leq \sum 2n\leq 100

对于 30%30\% 的数据,有 12n5001\leq \sum 2n\leq 500

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

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

对于 100%100\% 的数据,有 12n300001\leq \sum 2n\leq 30000