P5299 [PKUWC2018] Slay the Spire

Jiutiao Kelian is playing a very interesting strategy game: Slay the Spire. At the beginning, her deck contains $2n$ cards. Each card has a number $w_i$ written on it. There are two types of cards, with $n$ cards of each type: 1. Attack cards: After playing one, it deals damage equal to the number on the card. 2. Buff cards: After playing one, suppose the number on this buff card is $x$. Then the numbers on all remaining **attack cards** will be multiplied by $x$. **It is guaranteed that the numbers on buff cards are all greater than 1**. Now Jiutiao Kelian will randomly draw $m$ cards from the deck with equal probability. Due to energy limits, she can play at most $k$ cards. Assume she always uses the strategy that can deal the maximum damage. Find the expected damage she can deal. Suppose the answer is $\text{ans}$. You only need to output $$\left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353$$ Here, $x!$ means $\prod_{i=1}^{x}i$. In particular, $0!=1$.

The first line contains a positive integer $T$, denoting the number of test cases. For each test case: The first line contains three positive integers $n,m,k$. The second line contains $n$ positive integers $w_i$, representing the values on each buff card. The third line contains $n$ positive integers $w_i$, representing the values on each attack card.

Output $T$ lines. Each line contains a non-negative integer, representing the answer for each test case.

#### Sample Explanation For example, Jiutiao Kelian draws attack cards $\{1,2\}$ and a buff card $\{3\}$. The optimal strategy is to play the buff card $3$ first. Then the values of the attack cards become $\{3,6\}$, and then she plays $6$. #### Constraints For all testdata, $1\leq k\leq m\leq 2n\leq 3000$, and $1\leq w_i\leq 10^8$. **It is guaranteed that the numbers on buff cards are all greater than 1**. Let $(\sum 2n)$ denote the sum of $2n$ over all test cases in the input. For $10\%$ of the testdata, $1\leq \sum 2n\leq 10$. For $20\%$ of the testdata, $1\leq \sum 2n\leq 100$. For $30\%$ of the testdata, $1\leq \sum 2n\leq 500$. For another $20\%$ of the testdata, all attack cards have the same value. For another $20\%$ of the testdata, $m=k$. For $100\%$ of the testdata, $1\leq \sum 2n\leq 3000$. Translated by ChatGPT 5