概率期望

省流：期望 \(=\) 概率 \(\times\) 权值

好，开始看题。

题单

1.P4316 绿豆蛙的归宿

求在 \(\text{DAG}\) 上所走边权的期望，显然需要拓扑排序，有正推和逆退两种方式。

设 \(G\) 表示节点 \(u\) 直接相连节点的集合。

逆推

比较常用，需要建反图。

不难发现对于点 \(u\) 的期望，有：
\[E(u)=\sum_{v\in G}\left(\frac{1}{deg(u)}\times (E(v)+w)\right)\]

发现 \(deg(u)\) 恰好等于 \(G\) 的元素个数，因此上式等价于：
\[E(u)=w+\sum_{v\in G} \left(\frac{1}{deg(u)}\times E(v) \right)\]

int deg[maxn],_in[maxn];
queue q;
db f[maxn];
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add_edge(v,u,w);
        deg[u]++,_in[u]++;
    }
    q.push(n);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            _in[v]--;
            f[v]+=(f[u]+e[i].w)*1.0/deg[v];
            if(!_in[v]) q.push(v);
        }
    }
    printf("%.2f\n",f[1]);
    return 0;
}

正推

并非建正图就能解决，这里不能使用逆推中的化简式。
依旧是一般式：
\[E(u)=\sum_{v\in G}\left(\frac{1}{deg(v)}\times (E(v)+w)\right)\]
拆开来就是：
\[E(u)=\sum_{v\in G}\left(\frac{1}{deg(v)}\times E(v)\right)+\sum_{v\in G} \left(\frac{1}{deg(v)}\right)\times w\]
显然右半部分不一定为 \(w\)，所以要单独维护一个概率。

int deg[maxn],_in[maxn];
queue q;
db f[maxn],p[maxn];
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add_edge(u,v,w);
        deg[u]++,_in[v]++;
    }
    q.push(1);
    p[1]=1.00;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            _in[v]--;
            f[v]+=(f[u]+e[i].w*p[u])*1.0/deg[u];
            p[v]+=p[u]/deg[u]*1.0;
            if(!_in[v]) q.push(v);
        }
    }
    printf("%.2f\n",f[n]);
    return 0;
}

2.P4206 NOI2005 聪聪和可可

毒瘤题。

（1）预处理

来看两者的移动方法：

• 聪聪每次移动两步，最后一次可移动一步，每一步都会选择离可可最近且标号最小的节点
• 可可等概率移动一步或留在原地

显然聪聪的移动是个贪心，可以预处理出 \(pre(u,v)\) 表示聪聪和可可分别在 \(u,v\) 两点时聪聪应去到的节点。

稀疏图用 \(n\) 次已死算法 \(\text{SPFA}\) 只要判断最短路的松弛关系就能预处理出 \(pre\) 数组。

用 \(\text{dfs}\) 会迷之爆炸。

（2）递推

这里用到 \(\text{dfs}\) 其实是记忆化，设一个节点本身和与它直接相连的节点集 \(G\)，\(dp(u,v)\) 表示聪聪在节点 \(u\)，可可在节点 \(v\) 时的期望，就有：
\[dp(u,v)=\sum_{v\in G} \left(\frac{1}{deg(u)+1}\times (dp(pos,v)+1)\right)\]
其中 \(pos=pre(pre(u,v),v)\)，特别地令 \(dp(u,u)=0\)，所有对于能在两步以内到达的 \(（u,v）\)，令 \(dp(u,v)=1\)，然后大力记忆化暴搜。

不要用 \(vector\) 存图

int pre[1005][1005],dis[1005][1005];
db dp[1005][1005];
bool vis[1005],Vis[1005][1005];
inline void spfa(int s){
    memset(dis[s],0x3f,sizeof(dis[s]));
    dis[s][s]=0;
    vis[s]=1;
    queue q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[s][v]>dis[s][u]+1){
                dis[s][v]=dis[s][u]+1;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
inline db dfs(int x,int y){
    if(Vis[x][y]) return dp[x][y];
    Vis[x][y]=1;
    if(x==y) return dp[x][y]=0.0;
    int u=pre[x][y],v=pre[u][y];
    if(u==y||v==y) return dp[x][y]=1.0;
    dp[x][y]=1.0;
    for(int i=head[y];i;i=e[i].nxt){
        int z=e[i].to;
        dp[x][y]+=dfs(v,z)/(deg[y]+1);
    }
    dp[x][y]+=dfs(v,y)/(deg[y]+1);
    return dp[x][y];
}
int main(){
    n=read(),m=read();
    st=read(),ed=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++){
        spfa(i);
    }
    memset(pre,0x3f,sizeof(pre));
    for(int x=1;x<=n;x++){
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            for(int z=1;z<=n;z++){
                if(dis[x][z]==dis[y][z]+1) pre[x][z]=min(pre[x][z],y);
            }
        }
    }
    printf("%.3lf\n",dfs(st,ed));
    return 0;
}

3.P1654 OSU!

前置知识
\((\alpha+1)^2=\alpha^2+2\times \alpha +1\)
\((\alpha+1)^3=\alpha^3+3\times \alpha ^2+3\times \alpha +1\)

题目要求长度 \(n\) 的 \(0-1\) 串中 \(1\) 串长度的立方期望，考虑分步骤求解。

（1）前 \(i\) 位中第 \(i\) 位为 \(1\) 的线性期望

显然是由上一位得来，只考虑第 \(i\) 位是 \(1\) 的情况，那么线性期望 \(x_1\) 为：
\[x_1(i)=(x_1(i-1)+1)\times p_i\]

（2）前 \(i\) 位中第 \(i\) 位为 \(1\) 的平方期望

同上一问，依旧是只考虑第 \(i\) 位是 \(1\) 的情况，注意平方的期望与期望的平方存在差异，不能由第一问的结果直接得到。
\[x_2(i)=(x_2(i-1)+2\times x_1(i-1)+1)\times p_i\]

（3）前 \(i\) 位中第 \(i\) 位为 \(1\) 的立方期望

\[x_3(i)=(x_3(i-1)+3\times x_2(i-1)+3\times x_1(i-1)+1)\times p_i\]

（4）得解

第三问的结果仍不能作为答案，原因是我们只考虑最后一位是 \(1\) 的情况，答案实际为前 \(n\) 位的总和，这里需要分两部分，成功连接的概率是 \(p_i\)，反之概率是 \(1-p_i\)，于是有：
\[\begin{aligned} f(i)&=(f(i-1)+3\times x_2(i-1)+3\times x_1(i-1)+1)\times p_i+f(i-1)\times (1-p_i)\\ &= f(i-1)+(3\times x_2(i-1)+3\times x_1(i-1)+1)\times p_i \end{aligned}\]
发现最终答案与第三问无关，可以删去直接求最后结果。

int n;
db p;
db x1[maxn],x2[maxn],x3[maxn];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        scanf("%lf",&p);
        x1[i]=(x1[i-1]+1)*p;
        x2[i]=(x2[i-1]+x1[i-1]*2+1)*p;
        x3[i]=x3[i-1]+(x1[i-1]*3+x2[i-1]*3+1)*p;
    }
    printf("%.1lf\n",x3[n]);
    return 0;
}

4.P1365 WJMZBMR打osu! / Easy

同上一题，似乎更简单。

int n;
char s[maxn];
db len,ans;
int main(){
    n=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        db p;
        if(s[i]=='o') p=1.0;
        else if(s[i]=='x') p=0.0;
        else p=0.5;
        ans=ans+(len*2+1)*p;
        len=(len+1)*p;
    }
    printf("%.4lf\n",ans);
    return 0;
}

三倍经验

5.Red is good

用 \(dp(i,j)\) 表示 \(i\) 张红色，\(j\) 张黑色的期望得分，所谓最优策略就是期望为负时干脆一张牌也不翻。

db dp[5005][5005];
int main(){
    n=read(),m=read();
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i>0) dp[i][j]+=(dp[i-1][j]+1)*i*1.0/(i+j);
            if(j>0) dp[i][j]+=(dp[i][j-1]-1)*j*1.0/(i+j);
            if(dp[i][j]<0) dp[i][j]=0;
        }
    }
    printf("%.6lf\n",(int)(dp[n][m]*1e6)/1000000.0);
    return 0;
}

6.守卫者的挑战

设 \(dp(i,j,k)\) 表示前 \(i\) 个挑战，\(j\) 次成功，且剩余背包大小为 \(k\) 的概率。

这里的挑战要按获得的背包容积降序排序才能保证得到的碎片最大化的被带走。

答案为 \(\sum_{i=l}^n\sum_{j=0}^n dp(n,i,j)\)。

int n,m,w;
struct node{
    int num;
    db p;
    bool operator<(const node &rhs)const{
        return num>rhs.num;
    }
}a[205];
db dp[205][205][205],ans;
int main(){
    n=read(),m=read(),w=read();
    for(int i=1;i<=n;i++){
        int tmp=read();
        a[i].p=tmp*0.01;
    }
    for(int i=1;i<=n;i++){
        a[i].num=read();
    }
    dp[0][0][min(n,w)]=1;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        for(int j=0;j=0){
                    dp[i][j+1][min(n,k+a[i].num)]+=dp[i-1][j][k]*a[i].p;
                }
            }
        }
    }
    for(int i=m;i<=n;i++){
        for(int j=0;j<=n;j++){
            ans+=dp[n][i][j];
        }
    }
    printf("%.6lf\n",ans);
}

8.P1297 单选错位

首先预处理使得 \(a_{n+1}=a_i\)，答案为 \(\sum_{i=1}^n \frac{1}{\max(a_i,a_{i+1})}\)。

两种理解方式。

理解方式1

显然两两配对共有 \(a_i\times a_{i+1}\) 种情况，而匹配成功（相等）共有 \(min(a_i,a_{i+1})\) 种，于是概率为 \(\frac{\min(a_i,a_{i+1})}{a_i\times a_{i+1}}=\frac{1}{\max(a_i,a_{i+1})}\)。

理解方式 2

分三种情况讨论，正确概率等于所选答案在合理答案范围内的概率与所选答案匹配的概率之积。

• 若 \(a_i=a_{i+1}\)，显然概率为 \(\frac{1}{a_i}=\frac{1}{a_{i+1}}\);
• 若 \(a_i，则所选答案在 \(a_i\) 范围的概率 \(\frac{a_i}{a_{i+1}\)，匹配的概率 \(\frac{1}{a_i}\)，答案为 \(\frac{1}{a_{i+1}}\);
• 若 \(a_i>a_{i+1}\)，则所选答案在 \(a_i\) 范围内的概率为 \(1\)，答案即为匹配概率 \(\frac{1}{a_i}\)。

int A,B,C,n,a[maxn];
inline void Read(){
    scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
    for(int i=2;i<=n;i++)
        a[i]=((long long)a[i-1]*A+B)%100000001;
    for(int i=1;i<=n;i++)
        a[i]=a[i]%C+1;
}
db ans;
int main(){
    Read();
    a[n+1]=a[1];
    for(int i=1;i<=n;i++){
        ans+=1.0/max(a[i],a[i+1]);
    }
    printf("%.3f\n",ans);
    return 0;
}

9.列队春游

APJ:\(\text{视野距离}=\text{在他之前且连续低于他的小朋友个数}+1\)。

APJ：单独考虑每个小朋友，枚举比他低的小朋友，并且每个小朋友对答案的贡献最多为 \(1\)。

于是，设低于该小朋友的集合为 \(S\)，\(s=|S|\)，\(f_i\) 为第 \(i\) 个小朋友的期望（上述的个数），可以得到：
\[f_i=\sum_{j\in S} p_j\]

这个 \(p_j\) 显然为古典概型，总情况数 \(n!\)，先不考虑 \(s-1\) 个其他比 \(i\) 低的小朋友，把 \(i\) 与 \(k\) 看作整体（他们显然此时要相邻），就有 \(n-s\) 个元素，于是排列数 \((n-s)!\)，剩余的小朋友在 \(n\) 个位置上先放置，然后再补上已经排过的其他元素，于是概率为：
\[\frac{(n-s)!\times \mathrm{A}_ {n}^{s-1}}{n!}\]
化简得到：
\[\begin{aligned} f_i&=\sum_{j\in S}\frac{1}{n-s+1}\\ &=\frac{s}{n-s+1} \end{aligned}\]
之后求：
\[\sum_{h\in [1,1000]} tot_h\times \left(\frac{s}{n-s+1}+1\right)\]
也就是求：
\[\sum_{h\in [1,1000]} tot_h\times \left(\frac{n+1}{n-s+1}\right)\]

因为 \(h\) 范围很小，用个桶处理并不断更新 \(s\) 即可。

10.矩形粉刷

单独考虑点 \(E(i,j)\) 的期望并求 \(\sum_{i=1}^w\sum_{j=1}^h E(i,j)\)。
发现 \(k\) 次都不被染色的概率与被染色一次的概率之和为 \(1\)，那么不被染色的方案是，所选择的两点同在 \((i,j)\) 上方、下方、左边或右边，发现四个角会被计算两次，需要减去，快速幂得解即可。

inline ll sqr(int x){
    return pow(x,2);
}
inline db f(int x,int y){
    db tmp=(sqr((x-1)*h)+sqr((w-x)*h)+sqr(w*(y-1))+sqr(w*(h-y))-sqr((x-1)*(y-1))-sqr((x-1)*(h-y))-sqr((w-x)*(y-1))-sqr((w-x)*(h-y)))*1.0/sqr(w*h);
    return 1.0-q_pow(tmp,k);
}
db ans;
int main(){
    k=read(),w=read(),h=read();
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            ans+=f(i,j);
        }
    }
    printf("%.0lf\n",ans);
}

11.P2059 JLOI2013 卡牌游戏

设置 \(dp(i,j)\) 表示有 \(i\) 个人时，第 \(j\) 个最后人出局的概率，显然对应的答案应为 \(dp(n,i)\)。
对每个人作为庄家分别找到出局者，更新即可。

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        a[i]=read();
    }
    dp[1][1]=1.0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            _out=a[j]%i;
            if(!_out) _out=i;
            for(int k=1;ki) _out=1;
                dp[i][_out]+=dp[i-1][k]*1.0/m;
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%.2lf%% ",dp[n][i]*100.0);
    }
    return 0;
}

12.P1850 NOIP2016提高组 换教室

设置 \(dp(i,j,0/1)\) 表示前 \(i\) 堂课，申请换了 \(j\) 次教室，且第 \(i\) 次是否申请更换教室。

显然 \(dp(i,0,1)\) 是非法的，之后只需考虑每种转移状态对应的概率，方程过长，见代码。

int main(){
    n=read(),m=read(),v=read(),e=read();
    for(int i=1;i<=n;i++){
        c[i]=read();
    }
    for(int i=1;i<=n;i++){
        d[i]=read();
    }
    for(int i=1;i<=n;i++){
        scanf("%lf",&p[i]);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=e;i++){
        int u=read(),v=read(),w=read();
        dis[u][v]=min(dis[u][v],w);
        dis[v][u]=dis[u][v];
    }
    for(int k=1;k<=v;k++){
        for(int i=1;i<=v;i++){
            for(int j=1;j<=v;j++){
                if(i==k||j==k||i==j) continue;
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
    for(int i=1;i<=v;i++){
        dis[i][i]=dis[i][0]=dis[0][i]=0;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][0]=dp[i][j][1]=inf;
        }
    }
    dp[1][0][0]=dp[1][1][1]=0.0;
    for(int i=2;i<=n;i++){
        int c1=c[i-1],c2=c[i],d1=d[i-1],d2=d[i];
        dp[i][0][0]=dp[i-1][0][0]+dis[c1][c2];
        for(int j=1;j<=min(i,m);j++){
            dp[i][j][0]=Min(dp[i][j][0],dp[i-1][j][0]+dis[c1][c2],dp[i-1][j][1]+dis[c1][c2]*(1-p[i-1])+dis[d1][c2]*p[i-1]);
            dp[i][j][1]=Min(dp[i][j][1],dp[i-1][j-1][0]+dis[c1][c2]*(1-p[i])+dis[c1][d2]*p[i],
                            dp[i-1][j-1][1]+dis[c1][c2]*(1-p[i-1])*(1-p[i])+dis[c1][d2]*(1-p[i-1])*p[i]
                            +dis[d1][c2]*p[i-1]*(1-p[i])+dis[d1][d2]*p[i-1]*p[i]);
        }
    }
    for(int i=0;i<=m;i++){
        ans=Min(ans,dp[n][i][0],dp[n][i][1]);
    }
    printf("%.2lf\n",ans);
}

13.P2473 SCOI2008 奖励关

期望+状压dp

首先有了状压转移非常好像，当且仅当当前状态包含条件状态时可以增加权值，但问题出现在前 \(i\) 次未必能得到状态 \(S\)，考虑逆推即可。

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        val[i]=read();
        int x;
        while(scanf("%d",&x)&&x){
            sit[i]|=(1<<(x-1));
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<(1<

inline void dfs(int u,int fa){
    g[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        g[u]=g[u]*(1-f[v]*e[i].p);
    }
    f[u]=p[u]+(1-p[u])*(1-g[u]);
}  
inline void secdfs(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        db tmp;
        if(1-f[v]*e[i].p