更好的阅读体验&更新

前言

此文的题目均来源于luogu 期望标签下评级不高于蓝题（提高左右）的题目。

题目难度递增，前置很少，需要学会前缀和，DP，期望的基本定义，了解期望的线性性质即可。

性质并非笔记，类似做题记录或者说题解集合。

注释

本文中的期望都指数学期望。

• 定义：可能结果乘以概率的总和。比如投掷色子，结果为 $1\sim 5$，概率均为 $1/6$，期望就是 $1\times \dfrac{1}{6} +…+6\times \dfrac{1}{6}$
• 线性性质：$E(a+b)=E(a)+E(b)$ ，其中 $E$ 代表期望，$a,b$ 分别是两个事件。

P6154 游走

题目链接

题意

给定一个有向无环图，求其中一条路径长度的期望。

思路

对于一条路径，$E=\dfrac{sum}{cnt}$ ，$sum$ 为长度总和， $cnt$ 是路径个数。

考虑记忆化搜索。令 $f_i$ 表示 $i$ 开始的路径长度和， $g_i$ 表示路径条数。

那么 $f_i=\sum f_j+g_j,g_i=1+\sum g_j$ (加上自己到自己)

$ans=\dfrac{\sum f_i}{\sum g_i}$

代码

常数优化代码：

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int fmod( int x ) { x-=mod,x+=x>>31&mod; return x; }

不加优化的代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=7e5+10;
const ll mod=998244353;
struct edge
{
    int to,nxt;
}e[M];
int tot,head[N],n,m;
ll f[N],g[N];

void add( int u,int v )
{
    e[++tot]=(edge){v,head[u]}; head[u]=tot; 
}

ll power( ll a,ll b,ll P )
{
    ll res=1;
    for ( ; b; b>>=1,a=a*a%P )
        if ( b&1 ) res=res*a%P;
    return res;
}

void dp( int u )
{
    if ( g[u] ) return;
    g[u]=1;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to; dp( v );
        g[u]=(g[u]+g[v])%mod;
        f[u]=(f[u]+f[v]+g[v])%mod;
    }
}

int main()
{
    scanf( "%d%d",&n,&m );
    for ( int i=1,u,v; i<=m; i++ )
        scanf( "%d%d",&u,&v ),add( u,v );

    memset( g,0,sizeof(g) ); memset( f,0,sizeof(f) );
    for ( int i=1; i<=n; i++ )
        if ( !g[i] ) dp(i);
    ll s1=0,s2=0;
    for ( int i=1; i<=n; i++ )
        s1=(s1+f[i])%mod,s2=(s2+g[i])%mod;

    printf( "%lld\n",s1*power(s2,mod-2,mod)%mod );
}

P1850 换教室

题目链接

题意

有 n 节课程，如果申请通过则在 di 上课，否则在 ci，第 i 节课的通过概率是 ki。每个人至多选择 m 门课程申请。

学校为 v点e边的无向图，每条路有消耗的体力值，每次下课就选择最短路前往下一个教室。求耗费体力值的总和的最小期望值。

思路

令 $dp[i][j][0/1]$ 表示前 i 堂课申请了 j 次，第 i 堂课申请或不申请的最小期望花费。分类讨论。

• 如果第 i 堂课不申请：

• i-1 也不申请，那么期望花费是： $t1=f[c[i-1]][c[i]]$

• 申请，$t2=k[i-1]\times f[d[i-1]][c[i]]+(1-k[i-1])\times f[c[i-1]][c[i]]$

  结合起来就是：$dp[i][j][0]=min(dp[i-1][j][0]+t1,dp[i-1][j][1]+t2)$

• 第 i 堂课申请：

• i-1不申请 $t1=k[i]\times f[c[i-1]][d[i]]+(1-k[i])\times f[c[i-1]][c[i]]$

• i-1也申请

  • 都成功：$t2=k[i-1]\times k[i]\times f[d[i-1]][d[i]]$

  • i-1成功：$t3=k[i-1]\times (1-k[i])\times f[d[i-1]][c[i]]$

  • i 成功：$t4=(1-k[i-1])\times k[i]\times f[c[i-1]][d[i]]$

  • 没成功：$t5=(1-k[i-1])\times (1-k[i])\times f[c[i-1]][c[i]]$

总结一下就是：$dp[i][j][1]=min( dp[i-1][j-1][0]+t1,dp[i-1][j-1][1]+t2+t3+t4+t5$

边界：$dp[1][0][0]=0,dp[1][1][1]=0$

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2010,V=310;
const double inf=1e9+7;
double p[N],dis[V][V],f[N][N][2];
int c[N],d[N],n,m,v,e;

void get_dis()
{
    for ( int k=1; k<=v; k++ )
     for ( int i=1; i<=v; i++ )
      for ( int j=1; j<=v; j++ )
        dis[i][j]=dis[j][i]=min( dis[i][j],dis[i][k]+dis[k][j] );
}

void init()
{
    for ( int i=1; i<=v; i++ )
    {
        for ( int j=1; j<i; j++ )
            dis[i][j]=dis[j][i]=inf;
        dis[i][i]=0; dis[0][i]=0;
    }
    for ( int i=1; i<=n; i++ )
     for ( int j=0; j<=m; j++ )
        f[i][j][0]=f[i][j][1]=inf;
    f[1][0][0]=f[1][1][1]=0;
}

int main()
{
    scanf( "%d%d%d%d",&n,&m,&v,&e );
    for ( int i=1; i<=n; i++ )
        scanf( "%d",&c[i] );
    for ( int i=1; i<=n; i++ )
        scanf( "%d",&d[i] );
    for ( int i=1; i<=n; i++ )
        scanf( "%lf",&p[i] );
    init();
    for ( int i=1,u,v,w; i<=e; i++ )
        scanf( "%d%d%d",&u,&v,&w ),dis[u][v]=dis[v][u]=min( dis[u][v],(double)w );
    get_dis();

    for ( int i=2; i<=n; i++ )
     for ( int j=0; j<=min(i,m); j++ )
     {
        double t1=dis[c[i-1]][c[i]],t2=p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]];
        f[i][j][0]=min( f[i-1][j][0]+t1,f[i-1][j][1]+t2 );
        if ( j>0 )
        {
            t1=p[i]*dis[c[i-1]][d[i]]+(1-p[i])*dis[c[i-1]][c[i]];
            t2=p[i-1]*p[i]*dis[d[i-1]][d[i]];
            double t3=p[i-1]*(1-p[i])*dis[d[i-1]][c[i]];
            double t4=(1-p[i-1])*p[i]*dis[c[i-1]][d[i]];
            double t5=(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]];
            f[i][j][1]=min( f[i-1][j-1][0]+t1,f[i-1][j-1][1]+t2+t3+t4+t5 );
        }
     }

    double ans=inf;
    for ( int i=0; i<=m; i++ )
        ans=min( f[n][i][0],min( f[n][i][1],ans ) );
    printf( "%.2lf\n",ans );

    return 0;
}

P6059 纯粹容器

题目链接

题意

$n$ 个容器，每个强度为 $a_i$ （互不相同）.$n-1$ 轮操作，每次等概率选两个位置相邻且未被击倒的容器决斗，强度小的容器会被击倒并移出队列。求每个容器存活轮数的期望 $\mod 998244353.$

思路

首先特判，对于最大的 $a_i$ ，答案显然是 $n-1$ （不特判最小的原因是等概率选未必会选到它）。枚举每一个 $a_i$ ，找到距离 $a_i$ 最近且大于它的 $a_l,a_r$ ，显然 $a_i$ 被击倒只有 $[l,i] or[i,r]$ 之间的容器全部决斗。

枚举 $a_i$ 在第 $j$ 轮被淘汰，概率为 $p_{i,j}$ ，那么期望轮数就是 $\sum_{1\leq j<n} p_{i,j}\times(j-1)$

令 $calc(i,j)$ 表示 n-1 轮决斗中选出 $i$ 轮全部在前 $j$ 轮的概率。显然有 $calc(i,j)=\dfrac{j!(n-1-i)!}{(j-i)!(n-1)!}$

考虑怎么求 $p_{i,j}$ ，设 $g_{i,j}$ 表示 $a_i$ 在前 $j$ 轮就被淘汰的概率， $p_{i,j}=g_{i,j}-g_{i,j-1}$

对于 $g_{i,j}$ ，要么被左边淘汰，要么被右边淘汰，容斥得到:
$$g_{i,j}=calc(i-l,j)+calc(r-i,j)-calc(r-l,j)$$
（被左边淘汰+被右边淘汰+前 $j$ 轮淘汰了两次）

特判：如果某一边没有比它大的容器，那么只有一边淘汰，就是 $calc(i-l,j)$ 或者 $calc(r-i,j)$

代码

（居然判输出格式……cena用多了）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const int N=55;
int n,a[N];
ll inv[N],fac[N],g[N][N],ans[N];

ll power( ll a,ll b )
{
        ll res=1;
        for ( ; b; b>>=1,a=a*a%mod )
                if ( b&1 ) res=res*a%mod;
        return res;
}

void init()
{
        inv[0]=inv[1]=fac[1]=fac[0]=1;
        for ( int i=2; i<=n; i++ )
                fac[i]=fac[i-1]*i%mod;
        inv[n]=power( fac[n],mod-2 );
        for ( int i=n; i>1; i-- )
                inv[i-1]=inv[i]*i%mod;
}

ll calc( int i,int j )
{
        if ( i>j ) return 0;
        return fac[j]*fac[n-1-i]%mod*inv[j-i]%mod*inv[n-1]%mod;
}

int main()
{
        scanf( "%d",&n );
        for ( int i=1; i<=n; i++ )
                scanf( "%d",&a[i] );

        init(); memset( g,0,sizeof(g) );
        for ( int i=1; i<=n; i++ )
        {
                int l=i-1,r=i+1;
                while ( l>=1 && a[l]<a[i] ) l--;
                while ( r<=n && a[r]<a[i] ) r++;
                if ( l==0 && r==n+1 ) { ans[i]=n-1; continue; }
                if ( l==0 )
                {
                        for ( int j=1; j<n; j++ )
                                g[i][j]=calc( r-i,j );
                }
                else if ( r==n+1 )
                {
                        for ( int j=1; j<n; j++ )
                                g[i][j]=calc( i-l,j );
                }
                else 
                {
                        for ( int j=1 ;j<n; j++ )
                                g[i][j]=(calc( i-l,j )+calc( r-i,j )-calc( r-l,j )+mod)%mod;
                }
                for ( int j=1; j<n; j++ )
                        (ans[i]+=(g[i][j]-g[i][j-1]+mod)*(j-1)%mod)%=mod;
        }

        for ( int i=1; i<=n; i++ )
                printf( "%lld ",(ans[i]+mod)%mod );
}

P6835 [Cnoi2020]线形生物

题目链接

题意

起点为 $1$ ，走到 $n+1$ 停止，有 $n$ 条边，每条连接 $(i,i+1)$ ；外加 $m$ 条返祖边， $(u_i\to v_i)(u_i\ge v_i)$ 。每一步等概率走向一条出边。求总步数的期望 $E(\delta)\mod 998244353.$

思路

设 $E_{x,x+1}$ 表示 $x\to x+1$ 的期望步数。那么 $ans=\sum_{i=1}^n E_{i,i+1}.$

令 $d_x$ 表示 $x$ 的返祖边数目， $Edge$ 表示 $x$ 的返祖边集合。
$$E_{x,x+1}=\dfrac{1}{d_x+1}\times 1+\dfrac{1}{d_x+1}\sum_{(x,y)\in Edge} (E_{y,x+1}+1)$$
将 $E_{y,x+1}=\sum_{i=y}^x E_{i,i+1}$ 代入上面的式子，并化简：
$$E_{x,x+1}=1+\dfrac{1}{d_x+1} \sum_{(x,y)\in Edge}\sum_{i=y}^x E_{i,i+1}$$
设一类特殊的 $E$ ：$E_{x,x+1}$ 为 $f_x$ ,并记 $s_x=\sum_{i=0}^x f_i$ ，代入上式得到：
$$f_x=1+\dfrac{1}{d_x+1}\sum_{(x,y)\in Edge} (s_x-s_{y-1})$$
两边都含有项 $f_x$ ，那么把这一项全部移到等式左边：
$$f_x=1+\dfrac{1}{d_x+1}\sum_{(x,y)\in Edge}(s_{x-1}-s_{y-1})+\dfrac{1}{d_x+1}\times f_x\times d_x \\\\ f_x\times \dfrac{1}{d_x+1}=1+\dfrac{1}{d_x+1}\sum_{(x,y)\in Edge}(s_{x-1}-s_{y-1}) \\\\ f_x=d_x+1+\sum_{(x,y)\in Edge}(s_{x-1}-s_{y-1})$$
然后维护前缀和即可。时间复杂度 $O(n).$

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const ll mod=998244353;
struct edge
{
        int to,nxt;
}e[N];
int id,n,m,d[N],tot=0,head[N];
ll f[N],s[N];

void add( int u,int v )
{
        tot++; e[tot].to=v; e[tot].nxt=head[u]; head[u]=tot;
}

int main()
{
        scanf( "%d%d%d",&id,&n,&m );
        for ( int i=1,u,v; i<=m; i++ )
                scanf( "%d%d",&u,&v ),add( u,v ),d[u]++;

        s[0]=0;
        for ( int i=1; i<=n; i++ )
        {
                f[i]=d[i]+1;
                for ( int j=head[i]; j; j=e[j].nxt )
                        (f[i]+=(s[i-1]-s[e[j].to-1]+mod)%mod)%=mod;
                s[i]=(s[i-1]+f[i])%mod;
        }

        printf( "%lld",s[n] );
}