CF913F Strongly Connected Tournament 题解

题目链接：CF913F Strongly Connected Tournament

题意：

有 $n$ 个人，编号为 $1, 2, \cdots, n$ ，他们想要通过打架的方式决定他们的排名。

具体地，对于 $i < j$，$i$ 获胜的概率恒为 $p$。$p$ 通过给你两个非负整数 $A, B~(A \leq B),~p = \frac{A}{B}$ 的方式给出。

初始时，所有人都还没决出胜负。每一轮，对还未决出胜负的每一对人进行打架，得到一张竞赛图。将其进行缩点后，得到若干个 SCC（强连通分量）。

此时，如果两个人处在不同的 SCC 中，则它们已经决出胜负。否则，它们还未决出胜负 (下一轮还要继续)。

如果某一时刻所有人都决出胜负，则比赛结束，否则进行下一轮比赛。

你需要求出，这 $n$ 个人的比赛中打架次数的期望。

输入格式：

第一行包含一个正整数 $n~(n\le 3000)$，表示总人数。

第二行包含两个非负整数 $A, B~(0 \le A \le 100,B \neq 0)$ ，表示概率为 $p = \frac{A}{B}$。

输出格式：

输出一行一个整数，表示打架次数的期望在模 $998244353$ 意义下的结果。

综合性很强的dp题。

注意到每一轮比赛其实就相当于给无向完全图定向。

不难发现定向后一定是一张竞赛图。~~众所周知~~竞赛图缩点后为呈单向链状，每个点向其后所有点连边

因此我们可以根据套路（防止重复计算贡献），考虑拓扑序最靠前的那个 SCC（就是缩点后的点）。

具体地，设 $E_n$ 表示 $n$ 个点的无向完全图期望的打架次数， $F_n$ 表示 $n$ 个点的带权随机竞赛图的期望打架次数

这里的带权随机竞赛图指的就是 $p$ 概率定向为 $u\to v$ ，$q=1-p$ 概率定向为 $v \to u$ 的竞赛图

注意到一张无向完全图在一轮比赛后会增加 $\binom{n}{2}$ 次打架，然后转化为一张带权随机竞赛图，则

$E_n = F_n + \dbinom{n}{2}\tag{1} \label{1}$

考虑 $F_n$ 的转移。记刚刚提到的那个「拓扑序最靠前的那个 SCC」为 $S$ ，并记 $k = |S|$ 。

显然 $S$ 中的所有点构成了一个 SCC ，并且容易发现带权随机竞赛图的强连通性仅与其点数有关。

于是设 $n$ 个点的带权随机竞赛图强连通的概率为 $C_n$ 。

同时，注意到任意 $S$ 中的点与 $V \setminus S$ 中的点的连边一定为 $S$ 指向 $V \setminus S$ ，即

$\forall u \in S, ~\forall v \in (V \setminus S),~\exists!( u \to v) \tag{2}\label{2}$

记这个概率为 $\mathtt{cross}(S,~V\setminus S)$ 。

接着考虑 $V \setminus S$ 内部的连边，显然只与 $|V \setminus S|$ 有关，则它的打架次数期望应为 $F_{|V\setminus S|}$

$F_i=\sum_{S \subseteq V \land S \neq \varnothing} C_{|S|} \cdot \mathtt{cross}\left(S, ~V\setminus S\right) \cdot\left(E_{|S|}+F_{|V \setminus S|}\right) \tag{3} \label{3}$

注意到这里只有 $\mathtt{cross}(S,~V\setminus S)$ 与 $S$ 的具体构造有关，而其它项均与 $|S|$ 有关。

因此如果我们求出了以下式子

$\mathtt{cro}(k,~|V| - k) = \sum_{S \subseteq V \land |S| = k} \mathtt{cross}(S,~V\setminus S) \tag{4}\label{4}$

则原转移方程就转化为了仅与 $|S|$ 有关的式子，即

$F_i = \sum_{k = 1}^{i} C_k \cdot \mathtt{cro}(k,i-k)\cdot(E_k + F_{i-k}) \tag{5}\label{5}$

把 $\eqref{1}$ 代入 $\eqref {5}$ ，就能做到 $\mathcal{O}(n^2)$ 求 $F_n$ 了。

考虑如何求解 $\mathtt{cro}(n,m)$ 和 $C_n$ 。

首先 $C_n$ 是一个经典的容斥，考虑不强连通的情况，用 $1$ 减掉就好了（这里用 $\subset$ 表示真子集）

$C_i = 1 - \sum_{S\subset V \land S \ne \varnothing}C_{|S|} \,\cdot\,\mathtt{cross}(S,~V\setminus S) \tag{6} \label{6}$

也就是（~~拜拜容斥 qwq~~）

$C_i = \sum_{k=1}^{i-1}C_k \cdot \mathtt{cro}(k,i-k) \tag{7} \label{7}$

也可以在 $\mathcal{O}(n^2)$ 的时间内求出。最后就是 $\mathtt{cro}(n,m)$ 了，定义见 $\eqref{4}$ 。

显然一共有 $\binom{n+m}{n}$ 种情况，考虑其中最大的元素 $n+m$ 是属于 $S$ 还是属于 $V \setminus S$ 。

对于 $n+m$ 属于 $S$ 的 $\binom{n+m-1}{n-1}$ 种情况，与 $m$ 关联的边中，每条边方向正确的概率为 $q$ ，则概率为 $q^m$ 。

对于 $n+m$ 属于 $V \setminus S$ 的 $\binom{n+m-1}{m-1}$ 种情况，与 $m$ 关联的边中，每条边方向正确的概率为 $p$ ，则概率为 $p^n$ 。

则有

$\mathtt{cro}(n,m) = p^n\cdot\mathtt{cro}(n,m-1) + q^m\cdot \mathtt{cro}(n-1,m)\tag{8}\label{8}$

边界： $\mathtt{cro}(n,0) = \mathtt{cro}(0,n) = 1$ 。

然后这东西是有个封闭形式的。记

$u_1=1,~u_n = p^{n-1} + p^{n-2}q + \cdots + pq^{n-2} + q^{n-1} \tag{9}$

令 $U_n = \prod_{1 \le i \le n}u_i$ ，则有

$\mathtt{cro}(n,m) = \frac{U_{n+m}}{U_nU_m} \tag{10}$

证明用归纳法就可以了，~~不过怎么推出来的我也不清楚~~

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inv(x) (qpow((x), mod-2))
const int mod = 998244353, inv2 = (mod + 1) / 2;
void up(int &x, const int y) { x < y ? x = y : 0; }
void down(int &x, const int y) { x > y ? x = y : 0; }
void add(int &x, const int y) { (x += y) >= mod ? x -= mod : 0; }
int &Mod(int &x) { return x = (x < 0 ? (x % mod + mod) : (x % mod));}
#define N ((int)(3e3+150))

int n,A,B,p,q,pn,qn,pq,c=1;
int P[N],fy[N],fi[N],con[N],E[N],C[N];
int mul(int cnt, ...)
{
    va_list ptr; va_start(ptr,cnt); int res = 1;
    for(int i=0; i<cnt; i++) res = res * va_arg(ptr,int) % mod;
    va_end(ptr); return res;
}
int qpow(int a,int b)
{
    int ans = 1, base = a % mod;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % mod;
        base = base * base % mod;
    }
    return ans;
}
int cro(int a,int b) { return mul(3, fy[a+b], fi[a], fi[b]); }
int C2(int x) { return x * (x-1) / 2 % mod; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> A >> B;
    pn = p = A % mod * inv(B) % mod; qn = Mod(q = 1 - p);
    if(p == q)
    {
        for(int i=1; i<=n; i++, c = c * inv2 % mod)
            P[i] = i * c % mod;
    }else
    {
        pq = inv(p-q);
        for(int i=1; i<=n; i++, pn = pn * p % mod, qn = qn * q % mod)
            Mod(P[i] = (pn - qn) * pq % mod);
    }
    fy[0] = 1; for(int i=1; i<=n; i++) fy[i] = fy[i-1] * P[i] % mod;
    fi[n] = inv(fy[n]); for(int i=n; i; i--) fi[i-1] = fi[i] * P[i] % mod;
    con[1] = 1;
    for(int i=3,j; i<=n; Mod(con[i++]))
        for(con[i] = j = 1; j < i; j++)
            con[i] = (con[i] - con[j]*cro(j,i-j)) % mod;
    E[2] = C[2] = 1;
    for(int i=3,j; i<=n; i++)
    {
        for(c = C[i] = C2(i), j=1; j < i; j++)
            add(c, mul(3, cro(j,i-j), con[j], E[j] + E[i-j] - C[i-j]));
        Mod(E[i] = (c * inv(1-con[i]) % mod));
    }
    cout << E[n] << '\n';
    return 0;
}