P16281 「MierOI R1」Beyond

One day, Little M learned an algorithm called "fractional programming", which is used to solve the "fractional programming problem". :::info[Fractional Programming Problem]{open} There are $n$ items. The $i$-th item has a value of $a_i$ and a weight of $b_i$. Both $a_i$ and $b_i$ are positive integers. Select $k$ items from the $n$ items, let the selected items be $i_1,i_2,\dots,i_k$, and maximize the value of $$\frac{a_{i_1}+a_{i_2}+\dots+a_{i_k}}{b_{i_1}+b_{i_2}+\dots+b_{i_k}}$$ ::: Coincidentally, Little M had also solved a problem called [sale](https://www.luogu.com.cn/problem/P14636). On a whim, he came up with a problem to test you. Given $n,k$, and the value sequence $a$ of the items, find the number of possible weight sequences $b$ of the items **satisfying $\bm{1 \le b_i \le 2}$**, such that the following greedy strategy exactly finds the optimal solution to the "fractional programming problem": - Sort the items **in descending order of their values $\bm{a_i}$**. For items with the same value, sort them **in ascending order of their indices $\bm{i}$**. Select the top $k$ items after sorting. The answer should be modulo $998,244,353$.

**This problem contains multiple test cases.** The first line of the input contains a positive integer $T$, indicating the number of test cases. Then, the $T$ test cases follow sequentially. For each test case: - The first line contains two positive integers $n,k$. - The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$.

For each test case, output a single line containing a non-negative integer, representing the number of weight sequences $b$ satisfying the condition. The answer should be modulo $998,244,353$.

#### Explanation for Sample #1 For the first test case, the weight sequences $b$ satisfying the condition are $(1,1),(1,2),(2,2)$. When $b=(2,1)$, the greedy solution is $\frac{a_1}{b_1}=\frac{10}{2}=5$, and the optimal solution is $\frac{a_2}{b_2}=\frac{9}{1}=9$, so the greedy strategy fails to find the optimal solution. #### Data Range **This problem uses bundled subtasks.** For all test cases, it is guaranteed that $1 \le T \le 5$, $1 \le k \le n \le 2\,000$, and $1 \le a_i \le 10^9$. ::cute-table{tuack} | Subtask | $n \le$ | $k$ | Score | |:-:|:-:|:-:|:-:| | $1$ | $5$ | $\le n$ | $10$ | | $2$ | $16$ | ^ | $10$ | | $3$ | $40$ | ^ | $15$ | | $4$ | $200$ | ^ | $15$ | | $5$ | $2\,000$ | $=1$ | $5$ | | $6$ | ^ | $=2$ | $10$ | | $7$ | ^ | $=n-1$ | $5$ | | $8$ | ^ | $=n-2$ | $10$ | | $9$ | ^ | $\le n$ | $20$ |