专栏文章

【题录】概率与期望杂题

zzhouxianzhuo
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindqr6v
此快照首次捕获于
2025/12/02 00:44
3 个月前
此快照最后确认于
2025/12/02 00:44
3 个月前
查看原文

教室

题面

教室里有 nn 行 mm 列的学生，每个学生都有一个属性值，第 ii 行第 jj 列的学生的属性值为 vi,jv_{i,j}。
若属性值为 00，则说明这个学生一定会开小差。否则若其左方、前方、左前方三个位置中开小差的人数不小于其属性值，则其有 12\dfrac{1}{2} 的概率开小差。
现在老师想知道开小差人数的期望值是多少，答案对 998244353998244353 取模。
1≤n≤50,1≤m≤15,0≤vi,j≤31\le n\le50,1\le m\le15,0\le v_{i,j}\le3。

思路

根据期望的线性性，考虑计算每个学生开小差的概率并求期望相加，由于开小差时权值为 11，所以即求所有学生开小差的概率之和。
一个学生是否开小差仅取决于左方、前方、左前方三个位置，因此直接考虑轮廓线 DP，状压枚举轮廓线，刷表法转移到其它状态即可。

代码

CPP
#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;
}

未来

题面

未来中有 nn 个时空节点，它们构成一棵以第 11 个点为根的树，第 ii 个点有一个不稳定度 viv_i。
由于某些未知的原因，未来正在变得越来越不稳定。具体而言，设有一个 11 到 nn 的排列 PP，则第 ii 时刻，时空节点 PiP_i 会令其子树内所有节点（包括它自己）的不稳定度增加 vPiv_{P_i}。
PP 是 11 到 nn 的所有排列中等概率选出的，求第 nn 时刻后，所有时空节点不稳定度之和的期望值，答案对 998244353998244353 取模。
1≤n≤105,0≤vi<9982443531\le n\le10^5,0\le v_i<998244353。
树是随机生成的，其生成方法为随机生成一个 Prüfer 序列并将其转化为树。

思路

前置结论：通过随机生成 Prüfer 序列得到的树的平均树高约为 O(n)O(\sqrt{n})。
此结论提示我们可以对每个点枚举其所有祖先并计算贡献，发现枚举到的祖先对当前点的贡献的系数只与以此两点为两端的链有关，更进一步的，贡献的系数只与链的长度有关。
由上，设 fif_i 表示有一条长度为 ii 的链，其中第 ii 个点的权值为 11，其余点的权值为 00，以第 ii 个点为根如本题方式操作，最终得到的第 11 个点的权值的期望值。易得 fif_i 即为祖先与当前点间的链的长度为 ii 时的贡献系数。
递推求解 fif_i，枚举第 ii 个点之前有 jj 个点被操作，则这些操作都是无用的，即相当于在链上去掉了这 jj 个点，显然最终第 11 个点的权值和链上最左边的没被去掉的点的权值相等。接下来对第 ii 个点进行操作，此时会把剩下的 i−j−1i-j-1 个点的权值都变成 11。
设 gig_i 表示有一条长度为 ii 的链，其中所有点的权值都为 11，以第 ii 个点为根如本题方式操作，最终得到的第 11 个点的权值的期望值。
显然每个 jj 的概率为 1i\dfrac{1}{i}，由上得：
fi=1i⋅∑j=0i−1gi−j−1=1i⋅∑j=0i−1gj=1i⋅sumgi−1f_i=\frac{1}{i}\cdot\sum_{j=0}^{i-1}g_{i-j-1} \\ =\frac{1}{i}\cdot\sum_{j=0}^{i-1}g_{j} \\ =\frac{1}{i}\cdot sumg_{i-1}
而根据期望的线性性，得：
gi=∑j=1ifj=sumfig_i=\sum_{j=1}^if_j \\ =sumf_i
接下来对每个点枚举其祖先，计算其祖先的权值 vancv_{anc} 乘贡献系数 fdpx−dpanc+1f_{dp_x-dp_{anc}+1} 并求和即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,a[100010],dp[100010];
int hd[100010],ne[200010],to[200010],tot;
long long f[100010],ans;
vector<int> anc;
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;
}
void init(){
	f[1]=2;
	long long sf=2,sg=3;
	for(int i=2;i<=n;i++)
	{
		f[i]=sg*fp(i,mod-2)%mod;
		sf=(sf+f[i])%mod;
		sg=(sg+sf)%mod;
	}
	//预处理贡献系数 f 数组 
}
void add(int x,int y){
	tot+=1;
	ne[tot]=hd[x];
	hd[x]=tot;
	to[tot]=y;
}
void dfs(int x,int fa){
	dp[x]=dp[fa]+1;
	anc.push_back(x);
	//将当前点加入祖先链 
	for(int tx:anc)
		ans=(ans+f[dp[x]-dp[tx]+1]*a[tx])%mod;
	//枚举祖先并计算贡献 
	for(int i=hd[x];i>=1;i=ne[i])
	{
		if(to[i]==fa)continue;
		dfs(to[i],x);
	}
	anc.pop_back();
	//回溯时将当前点弹出祖先链 
}
int main(){
	scanf("%d",&n);
	init();
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dfs(1,0);
	//对每个点计算其所有祖先的贡献 
	printf("%lld",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...