题解

思路

记模数为 $M=998244353$，$p=a/b$，$q=1-p$。只要当前分组有 $i$ 人，编号的相对顺序仍然唯一决定任意一场比赛的胜率，因此其后续比赛期望只与 $i$ 有关。记这个期望为 $f_i$。

再记：

• $c_{i,j}$：从 $i$ 个有序顶点中选出 $j$ 个，使这 $j$ 个顶点全部输给其余顶点的概率之和；
• $s_i$：$i$ 个顶点形成强连通竞赛图的概率。

做法

子任务 1：枚举竞赛图

当 $n\le 6$ 时，每张竞赛图只有 $\binom n2\le 15$ 条边。枚举所有边的方向，用两次图遍历判断强连通，并按每张图的概率累加 $s_i$。再枚举顶点子集求 $c_{i,j}$，即可代入下文的期望递推。

复杂度为 $O(2^{\binom n2}n^2)$。

子任务 2：枚举顶点子集

固定 $i$ 和一个大小为 $j$ 的子集 $S$。要求所有 $S$ 中顶点输给补集顶点，跨越割的每条边方向就都被确定了，其概率是若干个 $p$ 与 $q$ 的乘积。枚举所有子集并累加，便能得到全部 $c_{i,j}$；随后按相同递推计算 $s_i,f_i$。

复杂度为 $O(2^n n+n^2)$，足以通过 $n\le18$。

子任务 3：二次动态规划

考虑加入编号最大的第 $i$ 个顶点。若它不在所选的 $j$ 个败者中，需要它战胜这 $j$ 人，贡献 $q^j$；若它在败者集合中，则前 $i-1$ 人中选择 $j-1$ 人，且它需要输给其余 $i-j$ 人，贡献 $p^{i-j}$。因此

$$c_{i,j}=c_{i-1,j}q^j+c_{i-1,j-1}p^{i-j},\qquad c_{i,0}=1.$$

竞赛图的强连通分量缩点后形成唯一的链。按链末端强连通分量的大小划分所有情况，可得

$$s_i=1-\sum_{j=1}^{i-1}s_jc_{i,j}.$$

若链末端分量大小为 $j<i$，本轮与后续贡献为

$$\binom j2+j(i-j)+f_j+f_{i-j}.$$

当整张图强连通时，本轮进行了 $\binom i2$ 场比赛，之后仍回到同样的 $i$ 人状态。于是

$$f_i=\sum_{j=1}^{i-1}s_jc_{i,j} \left(\binom j2+j(i-j)+f_j+f_{i-j}\right) +s_i\left(\binom i2+f_i\right).$$

移项得到

$$f_i=\frac{ \sum_{j=1}^{i-1}s_jc_{i,j} \left(\binom j2+j(i-j)+f_j+f_{i-j}\right) +s_i\binom i2}{1-s_i}.$$

所有除法均用模逆元完成。

复杂度

满分算法的总时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。