TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

25.9% (7/27)

Tags

Description

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

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

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

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

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

Input Format

第一行有三個數字$N, M, K$,第二行有$N$個數字,其中第$i$個數字代表$a_i$,第三行有$M$個數字,其中第$j$個數字代表$b_j$。

對於所有的測試資料,滿足$1 \leq K \leq N, M \leq 3000$,$1 \leq a_i, b_j \leq 10^ 9$,且對於所有的$i, j$,$a_i \not= b_j, a_i \not= a_j, b_i \not= b_j$。

特別地,
對於佔分$5\%$的測試資料來說,滿足$\min(a_i) > \max(b_j)$。
對於佔分$10\%$的測試資料,$N = M = 6$。
對於佔分$20\%$的測試資料,$K = 6$。
對於佔分$15\%$的測試資料,$1 \leq a_i, b_j \leq N + 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$局,否則會贏六局。故答案$\frac{1}{84} \cdot 5 + \frac{83}{84} \cdot 6 = \frac{503}{84}$。

$x \mod{K}$的意思為「 $x$ 除以 $K$ 的餘數」。若$ab \equiv 1 \mod 998244353$,則我們稱$b$為$a^ {-1}$。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~10 $\min(a_i) > \max(b_j)$ 5
2 11~20 $N = M = 6$ 10
3 21~30 $K = 6$ 20
4 31~40 $1 \leq a_i, b_j \leq N + M$ 15
5 0~50 $1 \leq N, M \leq 500$ 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