TopCoder

Caido
Waimai

User's AC Ratio

81.2% (26/32)

Submission's AC Ratio

39.6% (65/164)

Tags

Description

「神奇寶貝獎章」是一個最近很風行的手機遊戲——由於遊戲簡單,容易上手,又具有對戰、收集卡片等元素,很獲得某某高中二十六班的青睞,蔚為風潮。到了二十六班的你,就看到了兩個人在玩:

假設第一個人叫做沉驗如,他有N張牌,其中第i張牌有情侶度(CP)ai,而第二個人稱為辰玉胺,他則有M張牌,其中第j張有情侶度bj

透過良久的觀察,你逐漸推敲出了遊戲的規則。一場遊戲進行如下:

  1. 首先,兩個玩家會各自隨機從自己所有的牌中選出K張牌來,照情侶值排序好之後,依序出牌
  2. 接下來,他們會一一攤牌,遊戲總共進行 K 局,每次兩個人都將事先決定好的牌攤開,具有比較高的情侶度的牌勝。你也發現到,所有的牌的情侶度都相異,不會出現平手的事情。
  3. 最後, K 局中贏最多局者勝利!

現在,看出了你是程式和數學大師的沉驗如想要拜託你一件事:他已經事先知道,並告訴你辰玉胺的牌到底是哪些牌了,也告訴你他自己有哪些牌。你可以幫他算他所贏的局數的期望值為何嗎?可以證明,期望值可以表現成PQ,此處P0Q>0,且gcd(P,Q)=1。請輸出PQ1mod998244353。請注意,要算的是局數的期望值,並不是場數的期望值哦!

Input Format

第一行有三個數字N,M,K,第二行有N個數字,其中第i個數字代表ai,第三行有M個數字,其中第j個數字代表bj

對於所有的測試資料,滿足1KN,M5001ai,bj109,且對於所有的i,jaibj,aiaj,bibj

特別地,
對於佔分5%的測試資料來說,滿足min(ai)>max(bj)
對於佔分10%的測試資料,N=M=6
對於佔分20%的測試資料,K=6
對於佔分15%的測試資料,1ai,bjN+M

Output Format

請輸出一個數字,代表所求的答案。

Sample Input 1

6 6 6
101 102 103 104 105 106
1 2 3 4 5 6

Sample Output 1

6

Sample Input 2

9 6 6
6 7 8 9 10 11 13 14 15
1 2 3 4 5 12

Sample Output 2

344631985

Hints

對於第一筆範例,拿法只有一種,而且沉驗如每一局都會贏,所以答案為6。對於第二筆,如果選6 7 8 9 10 11會贏5局,否則會贏六局。故答案1845+83846=50384

xmodK的意思為「 x 除以 K 的餘數」。若ab1mod998244353,則我們稱ba1

9.9.2020 更新範圍

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~10 min(ai)>max(bj) 5
2 11~20 N=M=6 10
3 21~30 K=6 20
4 31~40 1ai,bjN+M 15
5 0~50 No additional constraints 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 5
1 1000 65536 262144 1 5
2 1000 65536 262144 1 5
3 1000 65536 262144 1 5
4 1000 65536 262144 1 5
5 1000 65536 262144 1 5
6 1000 65536 262144 1 5
7 1000 65536 262144 1 5
8 1000 65536 262144 1 5
9 1000 65536 262144 1 5
10 1000 65536 262144 1 5
11 1000 65536 262144 2 5
12 1000 65536 262144 2 5
13 1000 65536 262144 2 5
14 1000 65536 262144 2 5
15 1000 65536 262144 2 5
16 1000 65536 262144 2 5
17 1000 65536 262144 2 5
18 1000 65536 262144 2 5
19 1000 65536 262144 2 5
20 1000 65536 262144 2 5
21 1000 65536 262144 3 5
22 1000 65536 262144 3 5
23 1000 65536 262144 3 5
24 1000 65536 262144 3 5
25 1000 65536 262144 3 5
26 1000 65536 262144 3 5
27 1000 65536 262144 3 5
28 1000 65536 262144 3 5
29 1000 65536 262144 3 5
30 1000 65536 262144 3 5
31 1000 65536 262144 4 5
32 1000 65536 262144 4 5
33 1000 65536 262144 4 5
34 1000 65536 262144 4 5
35 1000 65536 262144 4 5
36 1000 65536 262144 4 5
37 1000 65536 262144 4 5
38 1000 65536 262144 4 5
39 1000 65536 262144 4 5
40 1000 65536 262144 4 5
41 1000 65536 262144 5
42 1000 65536 262144 5
43 1000 65536 262144 5
44 1000 65536 262144 5
45 1000 65536 262144 5
46 1000 65536 262144 5
47 1000 65536 262144 5
48 1000 65536 262144 5
49 1000 65536 262144 5
50 1000 65536 262144 5