CF913F Strongly Connected Tournament
题目描述
这是一个在 All-Right 城的国际象棋比赛。$n$ 个运动员被邀请参加比赛,比赛依照以下规则举办:
1. 起初,每个运动员与其他每一个运动员比赛,不存在平局的情况。
2. 在比赛之后,组织者造了一副有向的完全图,这张图把每名运动员看做点,对于每对运动员他们之间恰好有一条边:他们之间比赛的胜利者是这条边的起点,输了的人是终点。
3. 然后对原图进行缩点,缩点之后的图是一张无环完全图,这张图存在由原图的所有强连通分量组成的一条哈密顿路径,设为 $ A_{1} \rightarrow A_{2} \rightarrow \dots \rightarrow A_{k} $。
4. 之后对将强联通分量 $ A_{1} $ 里的点放到前 $\lvert A_{1} \rvert$ 个位置,将强联通分量 $A_{2}$ 中的所有点放入接下来 $\lvert A_{2} \rvert$ 个位置,以此类推。
5. 为了确定每个运动员在各自强联通分量中的排名,需要再在每个强联通分量中将不断地进行 $1 \sim 5$ 这五个步骤,也就是说,$A_{i}$ 中的 $k$ 个人都需要和其他的 $k-1$ 个人再比赛一次。
6. 如果一个强联通分量里只有一个人,那么他已经没有对手了,他的水平就已经确定了,就可以不用继续进行了。
运动员们被标号为 $1$ 到 $n$,标号被用在最初的图上。我们知道运动员 $i$ 能赢运动员 $j(i
输入格式
第一行是一个单独的整数 $n(n \le 2000)$,表示运动员的个数
第二行包括两个整数 $a$ 和 $b(1 \le a < b \le 100,\frac{a}{b}=p)$
输出格式
输出总比赛场数的期望值,对 $998244353$ 取模
如果对上面的定义很陌生点[这里](https://en.wikipedia.org/wiki/Strongly_connected_component)。
感谢 @doge233 提供的翻译。
说明/提示
第一个样例的期望值是 $4$。
第二个样例的期望值是 $\frac{27}{7}$。
第三个样例的期望值是 $\frac{56}{5}$。