【题目】F. Strongly Connected Tournament
【题意】给定n个点（游戏者），每轮游戏进行下列操作：
1.每对游戏者i和j（i<j）进行一场游戏，有p的概率i赢j（反之j赢i），连边从赢者向输者，从而得到一个有向完全图。
2.对于其中点数>1的强连通分量再次进行过程1，直至不存在点数>1的强连通分量为止。
给定n和p，求游戏总场次的期望。2<=n<=2000。
【算法】数学概率，期望DP
【题解】答案只和点数有关，设ans(n)表示n个点游戏总场次的期望，ans(0)=ans(1)=0。对于有向完全图，一定有且仅有一个出度为0的强连通分量，据此转移。（入度为0也行）
$$ans(n)=\sum_{i=1}^{n}s(i)*cp(n,i)*[ans(i)+ans(n-i)+i*(n-i)+\frac{i*(i-1)}{2}]$$
第一部分：首先选择i个点形成强连通分离，设s(i)表示i个点形成强连通分量的概率。
第二部分：然后这i个点必须是出度为0的强连通分量（拓扑序最后一个），换句话说必须被所有其它n-i个点打败。设cp(n,i)表示n个点中选i个点满足被其它n-i个点打败的概率。
第三部分：假设确定了最后一个强连通分量是i个点，那么这i个点进行了一轮游戏i*(i-1)/2，然后这i个点进入下一轮ans(i)，其它n-i个点视为正常继续游戏ans(n-i)，本轮游戏相互之间还有n*(n-i)场。
移项解方程。（cp(n,n)=1)
接下来计算cp(n,i)表示n个点中选i个点满足被其它n-i个点打败的概率，显然cp(n,0)=1。打败的概率和编号密切相关，所以通过依赖于点n的归属来计算：
$$cp(n,i)=p^{n-i}*cp(n-1,i)+(1-p)^i*cp(n-1,i-1)$$
第n个点要么是集合中的点，要么是集合外的点。
接下来计算s(n)表示n个点形成强连通分量的概率，显然s(1)=1。直接考虑形成强连通分量相当困难，换一种方式，按主方程一样考虑拓扑序最后一个强连通分量（如果大小不是n说明不是强连通分量）。
$$s(n)=1-\sum_{i=1}^{n-1}s(i)*cp(n,i)$$
复杂度O(n^2)。
#include<cstdio>
#include<algorithm>
using namespace std;
const int MOD=,maxn=;
int n,a,b,p,q,pp[maxn],qq[maxn],cp[maxn][maxn],strong[maxn],ans[maxn];
int M(int x){return x>=MOD?x-MOD:x;}
int power(int x,int k){
int ans=;
while(k){
if(k&)ans=1ll*ans*x%MOD;
x=1ll*x*x%MOD;
k>>=;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&a,&b);
p=1ll*a*power(b,MOD-)%MOD;
q=M(-p+MOD);
pp[]=qq[]=;
for(int i=;i<=n;i++)pp[i]=1ll*pp[i-]*p%MOD,qq[i]=1ll*qq[i-]*q%MOD;
cp[][]=;
for(int s=;s<=n;s++){
cp[s][]=;
for(int i=;i<=s;i++)cp[s][i]=M(1ll*cp[s-][i]*qq[i]%MOD+1ll*cp[s-][i-]*pp[s-i]%MOD);
}
strong[]=;
for(int s=;s<=n;s++){
for(int i=;i<s;i++)strong[s]=M(strong[s]+1ll*strong[i]*cp[s][i]%MOD);
strong[s]=M(-strong[s]+MOD);
}
ans[]=ans[]=;
for(int s=;s<=n;s++){
ans[s]=;
for(int i=;i<s;i++){
a=1ll*strong[i]*cp[s][i]%MOD;
b=(i*(s-i)+i*(i-)/+ans[i]+ans[s-i])%MOD;
ans[s]=M(ans[s]+1ll*a*b%MOD);
}
ans[s]=1ll*M(ans[s]+1ll*strong[s]*s*(s-)/%MOD)*power(M(-strong[s]+MOD),MOD-)%MOD;
}
printf("%d",ans[n]);
return ;
}