2168 . 神奇寶貝獎章 Hard
TopCoder
Tags
Description
「神奇寶貝獎章」是一個最近很風行的手機遊戲——由於遊戲簡單，容易上手，又具有對戰、收集卡片等元素，很獲得某某高中二十六班的青睞，蔚為風潮。到了二十六班的你，就看到了兩個人在玩：
假設第一個人叫做沉驗如，他有$N$張牌，其中第$i$張牌有情侶度（CP）$a_i$，而第二個人稱為辰玉胺，他則有$M$張牌，其中第$j$張有情侶度$b_j$。
透過良久的觀察，你逐漸推敲出了遊戲的規則。一場遊戲進行如下：
- 首先，兩個玩家會各自隨機從自己所有的牌中選出$K$張牌來，照情侶值排序好之後，依序出牌。
- 接下來，他們會一一攤牌，遊戲總共進行 $K$ 局，每次兩個人都將事先決定好的牌攤開，具有比較高的情侶度的牌勝。你也發現到，所有的牌的情侶度都相異，不會出現平手的事情。
- 最後， $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
101 102 103 104 105 106
1 2 3 4 5 6
Sample Output 1
Sample Input 2
6 7 8 9 10 11 13 14 15
1 2 3 4 5 12
Sample Output 2
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 |