P7592 Tree Counting (2021 CoE-II E)

Define a tree $\mathcal T$ to be a $k_1-k_2$-ary tree if and only if every node $p \in \mathcal T$ that has children has either $k_1$ children or $k_2$ children, with $k_1 \ne k_2$. We define two $k_1-k_2$ trees to be isomorphic if and only if the strings returned by the following pseudocode are the same: $$ \begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the tree } \mathcal T \\ 2 & \textbf{Output. } \text{The eigenvalue of tree } \mathcal T.\\ 3 & \textbf{Algorithm. } \text{dfs}(u)\\ 4 & \qquad result \gets \texttt{'('} \\ 5 & \qquad \textbf{for} \text{ each } (u, v) \text{ in the } \mathcal T \\ 6 & \qquad \qquad \textbf{if } v \text{ is not the father of } u \\ 7 & \qquad \qquad\qquad result \gets result\ +\ \mathrm{dfs}(v) \\ 8 & \qquad result\gets result\ +\ \texttt{')'} \\ 9 & \qquad \textbf{return } result \\ 10 & \textbf{Method. } \text{check}(\mathcal T) \\ 11 & \qquad \textbf{return } \text{dfs(the root of the tree } \mathcal T\text{)} \end{array} $$ Formally, a $k_1-k_2$-ary tree has a **fixed root**, the children of each node are **ordered**, but the nodes are **unlabeled**. If a $k_1-k_2$-ary tree $\mathcal T$ has a $k_1$-branching node, it gains score $a$; if it has a $k_2$-branching node, it gains score $b$; leaf nodes give no score. Define the score of a tree as the sum of the scores of all its nodes, denoted by $v(\mathcal T)$. Now, among all pairwise non-isomorphic $k_1-k_2$-ary trees with $n$ nodes, we generate one tree $\mathcal T$ uniformly at random. Let the expected value of $v(\mathcal T)$ be $\mathbb{E}(v(\mathcal T))$. It can be proven that $\mathbb{E}(v(\mathcal T))$ is a rational number. When $\mathbb{E}(v(\mathcal T)) \ne 0$, write $\mathbb{E}(v(\mathcal T)) = p/q$, where $p$ and $q$ are coprime. You need to output the smallest natural number $x$ such that $p \equiv qx \pmod P$, where $P = 998244353$. It can be proven that such a natural number $x$ must exist.

The input contains five integers $k_1,\ k_2,\ n,\ a,\ b$, with meanings as described above.

Output an integer $x$, the smallest natural number solution to $p \equiv qx \pmod P$, where $P = 998244353$.

**Sample Explanation.** There are $5$ non-isomorphic $2-3$-ary trees with $6$ nodes. Each tree has score $3$, so $\mathbb{E}(v(\mathcal T)) = 15/5 = 3$. Therefore $p = 3$ and $q = 1$, so $x = 3$.  ------------ **Constraints** There are $10$ test points in total. For test point $1$, $1 \le k_1,\ k_2 < n \le 10$. For test point $2$, $1 \le k_1,\ k_2 < n \le 15$. For test points $3 \sim 4$, $1 \le k_1,\ k_2 < n \le 5 \times 10^3$. For test points $5 \sim 6$, $a = b = 1,\ 1 \le k_1,\ k_2 < n \le 10^5$. For $100\%$ of the testdata, $1 \le k_1,\ k_2 < n \le 10^7,\ k_1 \ne k_2,\ k_1 + k_2 \le n,\ 1 \le a,\ b \le 10^7$. ------------ **Notes** - The testdata guarantees that $\mathbb{E}(v(\mathcal T)) \ne 0$. Translated by ChatGPT 5