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;
}