设 q = 1 − p q=1-p q=1−p， p p p的含义与题目相同。
首先设 g i g_i gi表示 i i i个点的竞赛图，内部还是一个SCC，期望打多少场分成一条链。
设 f i f_i fi表示 i i i个点的竞赛图，内部是一个SCC，打一轮之后还是一个SCC的概率。
然后是一般竞赛图DP的一个套路，设 d p i , j dp_{i,j} dpi,j表示 i i i个点的竞赛图，本来是一个SCC，打一轮之后最低的 j j j个点被剩下的所有点吊打的概率，注意，我们并不要求这些点形成一个SCC，允许形成多个SCC。
那么新加一个标号最大的点，考虑他是否属于被吊打点的集合，我们可以得到一个转移： d p i , j = d p i − 1 , j ⋅ p j + d p i − 1 , j − 1 ⋅ q i − j dp_{i,j}=dp_{i-1,j}\cdot p^j+dp_{i-1,j-1}\cdot q^{i-j} dpi,j=dpi−1,j⋅pj+dpi−1,j−1⋅qi−j
相应的，我们只需要考虑最低的SCC的大小即可得到 f f f：
f i = 1 − ∑ j = 1 i − 1 d p i , j f j f_i=1-\sum_{j=1}^{i-1}dp_{i,j}f_j fi=1−j=1∑i−1dpi,jfj
但是注意到如果我们要求 g i g_i gi，除了最低的那个SCC，上面剩下的点还要继续考虑，但是它们可能已经形成了一些SCC。注意到我们定了上面所有的点吊打下面，但是上面点之间的关系目前是任意的。
设 h i h_i hi表示 i i i个点的竞赛图，在打了一轮之后所有可能的情况下，打到只剩一条链的期望步数。
于是可以对期望列方程，移项得到：
g i = 1 1 − f i ( ( i 2 ) + ∑ j = 1 i − 1 d p i , j f j ( g j + h i − j ) ) h i = f i g i + ∑ j = 1 i − 1 d p i , j f j ( g j + h i − j ) g_i=\frac{1}{1-f_i}({i\choose 2}+\sum_{j=1}^{i-1}dp_{i,j}f_j(g_j+h_{i-j}))\\ h_i=f_ig_i+\sum_{j=1}^{i-1}dp_{i,j}f_j(g_j+h_{i-j}) gi=1−fi1((2i)+j=1∑i−1dpi,jfj(gj+hi−j))hi=figi+j=1∑i−1dpi,jfj(gj+hi−j)
挺套路的竞赛图DP，有的森林DP差不多也是这个套路。
代码：
#include<bits/stdc++.h> #define ll long long #define re register #define cs const cs int mod=998244353; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;} inline int power(int a,int b,int res=1){ for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a)); return res; } inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;} inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;} inline void Mul(int &a,int b){a=mul(a,b);} inline int C2(ll x){return x*(x-1)/2%mod;} cs int N=2e3+7; int n,p,q; int pw_p[N],pw_q[N]; int dp[N][N]; int f[N],g[N],h[N]; signed main(){ scanf("%d%d%d",&n,&p,&q); Mul(p,power(q,mod-2));q=dec(1,p); pw_p[0]=pw_q[0]=1; for(int re i=1;i<=n;++i) pw_p[i]=mul(pw_p[i-1],p), pw_q[i]=mul(pw_q[i-1],q); dp[0][0]=1; for(int re i=1;i<=n;++i) for(int re j=0;j<=i;++j) dp[i][j]=add(mul(dp[i-1][j],pw_p[j]),mul(j?dp[i-1][j-1]:0,pw_q[i-j])); for(int re i=1;f[i]=1,i<=n;++i) for(int re j=1;j<i;++j)Dec(f[i],mul(dp[i][j],f[j])); for(int re i=1;i<=n;++i){ for(int re j=1;j<i;++j){ int val=mul(mul(dp[i][j],f[j]),add(g[j],h[i-j])); Inc(g[i],val);Inc(h[i],val); } Inc(g[i],C2(i));Mul(g[i],power(dec(1,f[i]),mod-2)); Inc(h[i],mul(f[i],g[i])); } std::cout<<g[n]<<"\n"; return 0; }