#P7592. 数树(2021 CoE-II E)

数树(2021 CoE-II E)

题目描述

定义一棵树 T\mathcal Tk1k2k_1-k_2 叉树,当且仅当每个节点 pTp\in \mathcal T 有儿子,要么有 k1k_1 个儿子,要么有 k2k_2 个儿子,k1k2k_1 \ne k_2。我们定义两棵 k1k2k_1-k_2 树同构,当且仅当以下伪代码返回的字符串相同:

$$\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} $$

形式化地,k1k2k_1-k_2 叉树有确定的根节点,每个节点的若干儿子之间有顺序,但是节点没有标号

k1k2k_1-k_2 叉树 T\mathcal T 有一个 k1k_1 叉节点,则得分 aa,若有一个 k2k_2 叉节点,则得分 bb,叶节点无得分。定义一棵树的得分为其所有节点的得分之和,记为 v(T)v(\mathcal T)

现在我们在所有互不同构的 nn 个节点的 k1k2k_1-k_2 叉树中等概率随机生成一棵 T\mathcal T,记 v(T)v(\mathcal T) 的期望值为 E(v(T))\mathbb{E}(v(\mathcal T))

可以证明 E(v(T))\mathbb{E}(v(\mathcal T)) 为有理数。当 E(v(T))\mathbb{E}(v(\mathcal T)) 不为零时,令答案 E(v(T))=p/q\mathbb{E}(v(\mathcal T)) = p/q,其中 ppqq 互质。你需要输出最小的自然数 xx 使得 pqx(modP)p\equiv qx\pmod P,其中 P=998244353P=998244353,可以证明这样的自然数 xx 必定存在。

输入格式

输入包含五个整数 k1, k2, n, a, bk_1,\ k_2,\ n,\ a,\ b,其含义如题目描述所示。

输出格式

输出一个整数 xx,表示方程 pqx(modP)p\equiv qx\pmod P 的最小自然数解,其中 P=998244353P=998244353

2 3 6 1 2
3

提示

样例说明

具有 66 个结点的不同构 232-3 叉树共有 55 棵,每棵得分均为 33 分,则 E(v(T))=15/5=3\mathbb{E}(v(\mathcal T))=15/5=3,故 p=3p=3q=1q=1,则 x=3x=3


数据范围

1010 个测试点。

对于测试点 11,满足 1k1, k2<n101 \le k_1,\ k_2<n\leq 10

对于测试点 22,满足 1k1, k2<n151 \le k_1,\ k_2<n\leq 15

对于测试点 343\sim 4,满足 1k1, k2<n5×1031 \le k_1,\ k_2<n\leq 5 \times 10^3

对于测试点 565\sim 6,满足 a=b=1, 1k1, k2<n105a=b=1,\ 1 \le k_1,\ k_2<n\leq 10^5

对于 100%100\% 的数据,满足 $1 \le k_1,\ k_2<n\leq 10^7,\ k_1 \ne k_2, \ k_1+k_2 \le n, \ \ 1 \le \ a,\ b\leq 10^7$。


约定

  • 测试数据保证 E(v(T))\mathbb{E}(v(\mathcal T)) 不为零。