P15559 [CCPC 2025 Harbin Site] Matching

There are $n$ sets. The $i$-th set has $a_i$ elements. There are $2m$ pairwise distinct elements in total ($\sum a_i = 2m$). Each element belongs to exactly one set. In each round of operation, we randomly match all elements into $m$ pairs. For each pair, we randomly choose one element, remove it from its original set, and move it into the set that the matched element belongs to. Ask for the expected number of rounds of operations until all elements belong to one set. Output the answer modulo $998244353$.

The first line contains an integer $T$ ($1 \le T \le 100$), the number of testcases. Then for each testcase: Line $1$ contains two integers $n, m$ ($1 \le n \le 2m \le 400$), representing the initial number of sets and the number of pairs matched in each round. Line $2$ contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \times m$, $\sum a_i = 2 \times m$), where $a_i$ denotes the number of elements in the $i$-th set. It is guaranteed that over all testdata, $\sum n \le 800$ and $\sum m \le 400$.

For each testcase, output one integer per line representing the answer modulo $998244353$.

For Sample $1$: - Testcase 1: We represent the initial state as $[1,1]$. There is only $1$ possible matching, and no matter which of the $2$ elements is chosen, after one round the state becomes $[2]$. Therefore the expected answer is $1$. - Testcase 2: We represent the initial state as $[2,2]$. There are $3$ possible matchings. For each matching, there are $4$ ways to choose elements, so there are $12$ different operations in total. Among them, $4$ operations lead to state $[4]$, and the other $8$ operations lead to state $[2,2]$. That is, with probability $\frac{1}{3}$, after the operation only one set remains; otherwise the state does not change. Therefore the expectation is $3$. - Testcase 3: We represent the initial state as $[1,3]$. There are $12$ different operations in total. Among them, $6$ operations lead to state $[4]$, and the other $6$ operations lead to state $[2,2]$. Therefore the expectation is $1+\frac{1}{2}\times 3=\frac{5}{2}$, which is $499122179$ modulo $998244353$. - Testcase 4: We represent the initial state as $[1,1,2]$. There are $12$ different operations in total. Among them, $2$ operations lead to state $[4]$, and the other $10$ operations lead to state $[2,2]$. Therefore the expectation is $1+\frac{5}{6}\times 3=\frac{7}{2}$, which is $499122180$ modulo $998244353$. Translated by ChatGPT 5