【CodeForces】913 F. Strongly Connected Tournament 概率和期望DP

【题目】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 ;

}

巴特西

【CodeForces】913 F. Strongly Connected Tournament 概率和期望DP

最新文章

热门文章