#P18559. Quad Kingdoms Chess 2

Quad Kingdoms Chess 2

Quad Kingdoms Chess 2

四国棋(Quad Kingdoms Chess,简称 QKC)在技术锤子大学(Technical Hammer University,简称 THU)的 605A 宿舍中非常流行。

小青鱼在这所很棒的大学里有很多朋友。今天,经过一天的课程,小 X 和小 Y 决定下一盘四国棋。

图8:准备下四国棋

遗憾的是,他们没能凑齐四名玩家——小青鱼并不会下四国棋!为了找点乐子,他们各自随意拿了一组棋子,开始了比较棋子强弱的简化游戏。

每枚普通棋子用整数 si∈[1,105]s_i\in[1,10^5] 表示。小 X 和小 Y 各有一组棋子,按照以下规则进行对战:

  1. 最初,双方各自把棋子排成一个序列,再分别独立、均匀随机地打乱。
  2. 双方各派出自己序列中的第一枚棋子,分别记为 xx 和 yy。
  3. 若 x>yx>y,小 Y 的棋子被消灭,必须派出序列中的下一枚棋子;小 X 当前的棋子继续留在场上。
  4. 若 x<yx<y,小 X 的棋子被消灭,必须派出序列中的下一枚棋子;小 Y 当前的棋子继续留在场上。
  5. 若 x=yx=y,双方当前棋子都被消灭,双方都派出各自序列中的下一枚棋子。

在任何时刻,如果一方已经无法派出棋子,而另一方仍有至少一枚棋子,则仍有棋子的一方获胜。如果双方同时耗尽棋子,则为平局。

小青鱼觉得这太简单了!于是,在洗牌之前,他偷偷向小 X 的棋子中加入了 kk 枚额外的炸弹。也就是说,小 X 现在有 nn 枚普通棋子和 kk 枚炸弹,共 n+kn+k 枚棋子。炸弹与任意一枚对方棋子交战时,双方都被消灭。

给定双方的普通棋子,求小 X 获胜、小 Y 获胜以及平局的概率,对 998244353998244353 取模。

输入格式

第一行三个整数 n,m,kn,m,k(1≤n,m≤10001\le n,m\le1000,0≤k≤200\le k\le20),分别表示小 X 普通棋子的数量、小 Y 棋子的数量以及小青鱼加入的炸弹数量。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤1051\le a_i\le10^5),表示小 X 的普通棋子强度。

第三行 mm 个整数 b1,…,bmb_1,\ldots,b_m(1≤bj≤1051\le b_j\le10^5),表示小 Y 的棋子强度。

本题只有一组输入。相同强度的棋子可以重复。

输出格式

第一行输出 PXP_X,表示小 X 获胜的概率模 998244353998244353。

第二行输出 PYP_Y,表示小 Y 获胜的概率模 998244353998244353。

第三行输出 P=P_=,表示平局的概率模 998244353998244353。

若概率约分后为 p/qp/q,模意义的值为 p⋅q−1 mod 998244353p\cdot q^{-1}\bmod998244353,输出其 [0,998244353)[0,998244353) 内的代表元。

原样例 1

5 5 1
11 4 2 11 9
20 1 6 20 1
0
1
0

原样例 2

8 7 5
58 42 34 58 12 12 9 1
28 59 59 1 36 14 7
695057094
239873545
63313715

原样例 3

8 7 5
9 1 2 12 7 7 7 6
15 4 15 1 15 11 13
673575784
13961460
310707110