【题录】概率与期望杂题

zhouxianzhuo · 2025-11-04 18:55:15 · 个人记录

教室

题面

教室里有 n 行 m 列的学生，每个学生都有一个属性值，第 i 行第 j 列的学生的属性值为 v_{i,j}。

若属性值为 0，则说明这个学生一定会开小差。否则若其左方、前方、左前方三个位置中开小差的人数不小于其属性值，则其有 \dfrac{1}{2} 的概率开小差。

现在老师想知道开小差人数的期望值是多少，答案对 998244353 取模。

思路

根据期望的线性性，考虑计算每个学生开小差的概率并求期望相加，由于开小差时权值为 1，所以即求所有学生开小差的概率之和。

一个学生是否开小差仅取决于左方、前方、左前方三个位置，因此直接考虑轮廓线 DP，状压枚举轮廓线，刷表法转移到其它状态即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,a[55][20],f[55][16][65536];
long long inv2,ans;
long long fp(long long x,int k){
    long long s=1;
    while(k>=1)
    {
        if(k&1)s=s*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return s;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    }
    inv2=fp(2,mod-2);
    if(a[1][1]==0)f[1][1][1]=1;
    else f[1][1][0]=1;
    //对第一行第一列学生的提前处理 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int st=0;st<=(1<<(m+1))-1;st++)
            {
                if(f[i][j][st]==0)continue;
                //无贡献则直接跳过 
                if(st&(1<<(j-1)))ans=(ans+f[i][j][st])%mod;
                //计算答案 
                if(j<=m-1)
                {
                    int st1=st&((1<<j)-1),st2=(st>>(j+1))<<(j+1);
                    //提取出轮廓线左部和右部 
                    if(a[i][j+1]==0)
                    {
                        f[i][j+1][st1|st2|(1<<j)]=(f[i][j+1][st1|st2|(1<<j)]+f[i][j][st])%mod;
                        //必定开小差则直接转移 
                        continue;
                    }
                    int cnt=0;
                    if(st&(1<<(j-1)))cnt+=1;
                    if(st&(1<<j))cnt+=1;
                    if(st&(1<<(j+1)))cnt+=1;
                    if(cnt>=a[i][j+1])
                    {
                        f[i][j+1][st1|st2]=(f[i][j+1][st1|st2]+f[i][j][st]*inv2)%mod;
                        f[i][j+1][st1|st2|(1<<j)]=(f[i][j+1][st1|st2|(1<<j)]+f[i][j][st]*inv2)%mod;
                    }
                    //可能开小差的转移 
                    else f[i][j+1][st1|st2]=(f[i][j+1][st1|st2]+f[i][j][st])%mod;
                    //不可能开小差的转移 
                    continue;
                }
                //同一行向右转移的情况 
                if(i<=n-1)
                {
                    int st1=(st&((1<<m)-1))<<1;
                    //提取出轮廓线左部并右移 
                    if(a[i+1][1]==0)
                    {
                        f[i+1][1][st1|1]=(f[i+1][1][st1|1]+f[i][j][st])%mod;
                        //必定开小差则直接转移 
                        continue;
                    }
                    int cnt=0;
                    if(st&1)cnt+=1;
                    if(cnt>=a[i+1][1])
                    {
                        f[i+1][1][st1]=(f[i+1][1][st1]+f[i][j][st]*inv2)%mod;
                        f[i+1][1][st1|1]=(f[i+1][1][st1|1]+f[i][j][st]*inv2)%mod;
                    }
                    //可能开小差的转移 
                    else f[i+1][1][st1]=(f[i+1][1][st1]+f[i][j][st])%mod;
                    //不可能开小差的转移 
                }
                //向下一行第一列转移的情况 
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

未来

题面

未来中有 n 个时空节点，它们构成一棵以第 1 个点为根的树，第 i 个点有一个不稳定度 v_i。

由于某些未知的原因，未来正在变得越来越不稳定。具体而言，设有一个 1 到 n 的排列 P，则第 i 时刻，时空节点 P_i 会令其子树内所有节点（包括它自己）的不稳定度增加 v_{P_i}。