TopCoder

Caido
Waimai

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

25.9% (7/27)

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,M30001ai,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

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 1N,M500 20
6 0~60 No additional constraints 30

Testdata and Limits

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