Connectivity of Erdős-Rényi Graph

Yukikaze is studying the theory of random graphs.

In the probability version of the Erdős-Rényi model, a random graph is constructed by connecting nodes randomly. That is, the random graph $G(n,p)$ is an undirected graph with $n$ vertices, and each edge from the $\dfrac{n(n-1)}{2}$ possible edges is included in the graph with probability $p$ independently from every other edge.

Now she wonders about the expected number of connected components in $G(n,p)$, modulo a large prime $998244353$.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 100$), denoting the number of test cases.

The first line of each test case contains three integers $q,a,b$ ($1 \leq q \leq 10^5$, $1 \leq a \leq b < 998244353$), denoting the number of queires and the probability $p=a/b$.

The second line of each test case contains $q$ integers $n_1,n_2,\ldots,n_q$ ($1 \leq n_i < 5\times 10^5$ for each $1 \leq i \leq q$) seperated by spaces, denoting that Yukikaze wants to know the expected number of connected components in $G(n_i,p)$.

Let $N$ be the sum of the maximum $n_i$ of each test case, and $Q$ be the sum of $q$ of all test cases. It's guaranteed that $N \leq 5\times 10^5$ and $Q \leq 10^5$.

For each test case, output a single line containing the answers to the queries separated by spaces. You should output the answers modulo $998244353$. That is, if the answer is $\frac{P}{Q}$, you should output $P\cdot Q^{-1}\bmod 998244353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998244353$. We can prove that the answer can always be expressed in this form.

Don't output any extra spaces at the end of each line.

3
1 14 51
4
1 91 98
10
2 114 514
1919 810

798850218
132789114
904977379 493892762

2022“杭电杯”中国大学生算法设计超级联赛（7）