$CF\ vp$ 场.
$per$
用所有的方案 $n!$ 减去 $a$ 单调不减的方案,再减去 $b$ 单调不减的方案,再把 $a,b$ 都不减的方案加回来.
$medium$
记 $pr=\frac a b$ ,单场概率确定的情况下,答案只与点的个数有关.
设 $f(x)$ 表示有 $x$ 个点时,游戏总场次的期望.边界有 $f(0)=f(1)=0$ .
强连通分量在缩成一个点后,最终会形成一个 $\text{DAG}$ ,所以缩点前,一定存在一个出度为 $0$ 的强连通分量.
枚举这个出度为 $0$ 的强连通分量的大小进行转移.
$$
f(n)=\sum_{i=1}^n p(i)\cdot g(n,i)\cdot (f(i)+f(n-i)+i\cdot(n-i)+{i\choose 2})
$$
其中 $p(i)$ 表示 $i$ 个点形成强连通分量的概率, $g(n,i)$ 表示从 $n$ 个点中选出 $i$ 个点,被其他 $n-i$ 个点打败的概率.
注意到枚举时有 $f(n)$ 转移到自己的情况,所以要移项解方程来计算.
考虑如何计算 $g(n,i)$ ,枚举 $n$ 是被打败的 $i$ 个点中的一个,还是 $n-i$ 个点中的一个.
$$
g(n,i)=pr^{n-i}\cdot g(n-1,i)+(1-pr)^i \cdot g(n-1,i-1)
$$
考虑如何计算 $p(i)$ ,仍然像计算 $f(i)$ 那样,枚举出度为 $0$ 的强连通分量大小.
$$
p(n)=1-\sum_{i=1}^{n-1}p(i)\cdot g(n,i)
$$
时间复杂度 $O(n^2)$ .
$easy$
把每个套娃看成一个点, $a$ 能套住 $b$ 看做一条边 $a\to b$ ,权值是产生的空隙大小,即 $a_{in}-b_{out}$ .
直接连边的复杂度是 $O(n^2)$ ,把套娃按 $out$ 排序,每个套娃能连向的点是一段区间,可以线段树优化连边.
从 $S$ 向每个入度为 $0$ 的点连边权为 $0$ 的边,从每个出度为 $0$ 的点向 $T$ 连边权为 $x_{in}$ 的边.
那么要求的方案数就是从 $S$ 到 $T$ 的最短路数目,图是 $\text{DAG}$ ,可以直接记忆化搜索求出.