概率期望学习笔记

xtx1092515503 · 2020-09-15 21:49:01 · 个人记录

我 爱 数 学

突然发现我不会概率期望，就来补题了。

I.[CTSC2018]假面

期望第一题，居然能独立做出来。

首先这个数据范围明显是暗示我们一个O(Qm+Cn^2)的算法可以过去。

我们设pos_{i,j}表示敌人i剩余血量为j的概率。

则当使用一个“锁定”技能后，就相当于对pos_i做了一个背包，单次复杂度O(m_i)。

再考虑“结界”技能。

我们设一个f_i，表示该技能使用时，恰有i个人有血的概率。这个可以O(n^2)背包搞出来。

然后，再对于每个i，O(n)地从这个背包中“删掉”它。

需要注意的是，当i一定有血的时候，这个“删掉”操作与其它情况不同，需要特判一下。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int ksm(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
    return z;
}
int n,lim[210],q,pos[210][110],p[210],f[210],g[210],inv[210];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&lim[i]),pos[i][lim[i]]=1;
    for(int i=1;i<=n;i++)inv[i]=ksm(i,mod-2);
    scanf("%d",&q);
    for(int qwq=1,a,b,c,d;qwq<=q;qwq++){
        scanf("%d",&a);
        if(a==0){
            scanf("%d%d%d",&b,&c,&d),c=1ll*c*ksm(d,mod-2)%mod,d=(mod+1-c)%mod;
            (pos[b][0]+=1ll*pos[b][1]*c%mod)%=mod;
            for(int i=1;i<=lim[b];i++)pos[b][i]=(1ll*pos[b][i]*d+1ll*pos[b][i+1]*c)%mod;
        }else{
            scanf("%d",&b);
            for(int i=1;i<=b;i++)scanf("%d",&p[i]);
            for(int i=0;i<=b;i++)f[i]=0;
            f[0]=1;
            int zero=0;
            for(int i=1;i<=b;i++){
                c=pos[p[i]][0],d=(mod+1-c)%mod;
                if(!c){zero++;continue;}
                for(int j=i-zero;j>=0;j--){
                    f[j]=1ll*f[j]*c%mod;
                    if(j)(f[j]+=1ll*f[j-1]*d%mod)%=mod;
                }
            }
//          printf("P:");for(int i=1;i<=b;i++)printf("%d ",pos[p[i]][0]);puts("");
//          printf("F:");for(int i=0;i<=b;i++)printf("%d ",f[i]);puts("");
            for(int i=1;i<=b;i++){
                c=pos[p[i]][0],d=(mod+1-c)%mod;
                c=ksm(c,mod-2);
                for(int j=0;j<=b-zero;j++)g[j]=f[j];
                if(c){
                    for(int j=0;j<b-zero;j++){
                        g[j]=1ll*g[j]*c%mod;
                        (g[j+1]+=mod-1ll*g[j]*d%mod)%=mod;
                    }                   
                }
//              printf("%d:GGG",i);for(int j=0;j<b;j++)printf("%d ",g[j]);puts("");
                int res=0;
                for(int j=0;j<=b-zero;j++)(res+=1ll*inv[j+zero+(c!=0)]*g[j]%mod)%=mod;
                printf("%d ",1ll*res*d%mod);
            }puts("");
        }
    }
    for(int i=1;i<=n;i++){
        int res=0;
        for(int j=0;j<=lim[i];j++)(res+=1ll*pos[i][j]*j%mod)%=mod;
        printf("%d ",res);
    }
    return 0;
}

II.[HAOI2012]高速公路

本题已经在我的任务列表里挂了1年多了

我们将这里的“期望”转成“\dfrac{\text{区间中任意两点间距离之和}}{\text{区间中选取两点的方案数}}。然后，我们考虑使用线段树维护区间中任意两点间距离之和。

在每个节点上，我们维护如下东西：