概率和期望专题

Cyber_Punk / 2024-02-25 / 原文

概率和期望专题

FZOJ4878 [2021NOIP前模拟] 给国的桥梁

给国是一个神秘的国家，这个国家的 $n$ 个城市分别坐落在 $n$ 个岛上，通过 $m$ 座桥连接。
你通过任何一座桥都需要恰好 $1$ 的时间。在城市内的时间忽略不计。
不幸的是，给国的有些桥已经年久失修了。如果你经过一座年久失修的桥，你会直接掉入河中，然后等概率漂到这座桥连接的两个城市中的一个。
如果你掉入河中并漂到一个城市，也需要消耗恰好 $1$ 的时间。
你一开始并不知道哪些桥是年久失修的，只有经过一座桥后才知道这座桥的状态。
不过你通过统计发现每座桥恰好有 $\dfrac{1}{2}$ 的概率是年久失修的。当然当你经过一座桥后，这座桥的状态（是不是年久失修）就确定了。
现在你需要从 $1$ 号点出发到 $n$ 号点。你想要知道在最优策略下，你期望需要多少时间。
对于所有测试点，保证给定的图是一张无自环的连通图，可能会有重边，$2\leq n, m\leq 2\times 10^5$。

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define N 200010
int n,m;
int mark[N],cnt[N];
double dist[N],pre[N],E[N];
vector <int> G[N];
struct Node
{
	int id;
	double val;

	bool operator < (const Node &rhs) const
	{
		return val>rhs.val;
	}

};
priority_queue <Node> Heap;

int read ()
{
	int k=1,s=0;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
	return k*s;
}

void Dijkstra ()
{
	Heap.push ((Node) {n,0});
	while (!Heap.empty ())
	{
		int x=Heap.top ().id;
		Heap.pop ();
		if (mark[x]) continue;
		mark[x]=1;
		for (int y: G[x])
		{
			if (mark[y]) continue;
			if (!cnt[y])
			{
				dist[y]=dist[x]+1.5;
				pre[y]=dist[x];
				cnt[y]++;
				E[y]=0.25;
				Heap.push ((Node) {y,dist[y]});
			}
			else
			{
				if (dist[x]+1.5>pre[y]+2.0) continue;
				dist[y]-=E[y]*(cnt[y]+pre[y]+2.0);
				cnt[y]++;
				dist[y]+=0.75*E[y]*(cnt[y]+dist[x]);
				dist[y]+=0.25*E[y]*(cnt[y]+pre[y]+2.0);
				E[y]*=0.25;
				Heap.push ((Node) {y,dist[y]});
			}
		}
	}
}

void Init ()
{
	n=read (),m=read ();
	for (int i=1;i<=m;i++)
	{
		int x=read (),y=read ();
		G[x].emplace_back (y);
		G[y].emplace_back (x);
	}
}

void Work ()
{
	Dijkstra ();
	printf ("%.12lf\n",dist[1]);
}

signed main ()
{
	Init ();
	Work ();
	return 0;
}

luoguP5405 [CTS2019] 氪金手游

小刘同学是一个喜欢氪金手游的男孩子。
他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知：
$1.$ 卡池里总共有 $N$ 种卡，第 $i$ 种卡有一个权值 $W_i$，小刘同学不知道 $W_i$ 具体的值是什么。但是他通过和网友交流，他了解到 $W_i$ 服从一个分布。
$2.$ 具体地，对每个 $i$，小刘了解到三个参数 $p_{i,1},p_{i,2},p_{i,3}$，$W_i$ 将会以 $p_{i,j}$ 的概率取值为 $j$，保证 $p_{i,1}+p_{i,2}+p_{i,3}=1$。
小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 $i$ 的概率为： $$\frac{W_i}{\sum_j W_j}$$ 小刘会不停地抽卡，直到他手里集齐了全部 $N$ 种卡。
抽卡结束之后，服务器记录下来了小刘第一次得到每张卡的时间 $T_i$。游戏公司在这里设置了一个彩蛋：公司准备了 $N-1$ 个二元组 $(u_i,v_i)$，如果对任意的 $i$，成立 $T_{u_i}<T_{v_i}$，那么游戏公司就会认为小刘是极其幸运的，从而送给他一个橱柜的手办作为幸运大奖。
游戏公司为了降低获奖概率，它准备的这些 $(u_i,v_i)$ 满足这样一个性质：对于任意的 $\varnothing\ne S\subsetneq\{1,2,\ldots,N\}$，总能找到 $(u_i,v_i)$ 满足：$u_i\in S,v_i\notin S$ 或者 $u_i\notin S,v_i\in S$。
请你求出小刘同学能够得到幸运大奖的概率，可以保证结果是一个有理数，请输出它对 $998244353$ 取模的结果。
对于全部的测试数据，保证 $N\le 1000$，$a_{i,j}\le 10^6$。

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 3010
const int mod=998244353;
int n,tot,head[N];
int inv[N];
int siz[N],F[N][N],_F[N];
struct Node
{
	int nxt,to;
}edge[N];

int read ()
{
	int k=1,s=0;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
	return k*s;
}

int Qpow (int x,int y)
{
	int res=1;
	while (y>0)
	{
		if (y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return res;
}

void AddEdge (int x,int y)
{
	edge[++tot]=(Node) {head[x],y};
	head[x]=tot;
}

void DFS (int x,int from)
{
	siz[x]=1;
	for (int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if (y==from) continue;
		DFS (y,x);
		for (int j=1;j<=3*siz[x];j++)
			_F[j]=F[x][j],F[x][j]=0;
		for (int j=1;j<=3*siz[x];j++)
			for (int k=1;k<=3*siz[y];k++)
			{
				if (i&1) F[x][j+k]=(F[x][j+k]+1ll*_F[j]*F[y][k]%mod)%mod;
				else
				{
					F[x][j+k]=(F[x][j+k]-1ll*_F[j]*F[y][k]%mod+mod)%mod;
					F[x][j]=(F[x][j]+1ll*_F[j]*F[y][k]%mod)%mod;
				}
			}
		siz[x]+=siz[y];
	}
	for (int i=1;i<=3*siz[x];i++)
		F[x][i]=1ll*F[x][i]*inv[i]%mod;
}

void Init ()
{
	n=read ();
	inv[1]=1;
	for (int i=2;i<=3*n;i++)
		inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod+mod)%mod;
	for (int i=1;i<=n;i++)
	{
		int x=read (),y=read (),z=read ();
		int w=Qpow (x+y+z,mod-2);
		F[i][1]=1ll*x*w%mod;
		F[i][2]=2ll*y*w%mod;
		F[i][3]=3ll*z*w%mod;
	}
	for (int i=1;i<n;i++)
	{
		int x=read (),y=read ();
		AddEdge (x,y);
		AddEdge (y,x);
	}
}

void Work ()
{
	DFS (1,0);
	int ans=0;
	for (int i=1;i<=3*n;i++)
		ans=(ans+F[1][i])%mod;
	printf ("%d\n",ans);
}

signed main ()
{
	Init ();
	Work ();
	return 0;
}

FZOJ5406 [2023NOIP前模拟] 积云四月

小 Y 眼中的天空是一个 $n\times m$ 的平面，每个位置可能有一朵积雨云。
小 Y 用一个 $n\times m$ 的 $01$ 矩阵 $Q$ 来表示积雨云的存在，$Q_{i,j}=1$ 代表位置 $(i,j)$ 有一朵积雨云，$Q_{i,j}=0$ 代表位置 $(i,j)$ 没有积雨云。
积雨云显然是会合并的。
小 Y 认为积雨云 $A(x_1,y_1),B(x_2,y_2)$ 是可合并的，当且仅当 $x_1=x_2$ 或者 $y_1=y_2$。
当两朵积雨云合并之后，他们都会消散。
在一天天的观察中，小 $Y$ 发现，每一种初始的积雨云分布最终剩下的积雨云个数一定是所有可能的情况中最少的，这样才会使得积雨云变得稳定。
记 $C(Q)$ 为对于初始分布$Q$ ，最终变得稳定时的积雨云个数。
给定一个矩阵 $P_{i,j}$，$Q_{i,j}$ 有 $P_{i,j}$ 的概率为 $1$，$1-P_{i,j}$ 的概率为 $0$。
请你求出 $C(Q)$ 的期望在模 $p$ 意义下的值。
对于 $100\%$ 的数据，$n\leq 8,m\leq 8,0 \leq Q_{i,j} \leq p-1,10^5\leq p\leq 10^9,p$ 是质数。

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define Int __int128
#define int long long
#define N 11
#define M 1<<16
int T,n,m,V,mod,a[N][N],b[N][N];
int cnt[M],E[M],I[M];
int H[M][2],F[M][2],G[M];

int read ()
{
	int k=1,s=0;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
	return k*s;
}

int Qpow (int x,int y)
{
	int res=1;
	while (y>0)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;y>>=1;
	}
	return res;
}

int Calc (int s,int t)
{
	if (cnt[s^t]+cnt[t]<cnt[s]) return 0;
	return (Int) E[s]*I[s^t]*I[t]%mod;
}

void Init ()
{
	n=read ();m=read ();mod=read ();
	V=n+m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			a[i][j]=read ();
			b[i][j]=Qpow ((1-a[i][j]+mod)%mod,mod-2);
		}
}

void Work ()
{
	for (int s=0;s<(1<<V);s++)
	{
		H[s][0]=1;
		H[s][1]=0,G[s]=0,cnt[s]=0;
	}
	for (int s=0;s<(1<<V);s++)
	{
		int resE=1,resI=1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				if (s&(1<<(i-1)) && s&(1<<(n+j-1)))
				{
					if (a[i][j]==1) cnt[s]++;
					else
					{
						resE=resE*(1-a[i][j]+mod)%mod;
						resI=resI*b[i][j]%mod;
					}
				}
		E[s]=resE%mod,I[s]=resI%mod;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			for (int s=(1<<V)-1;s>0;s--)
				if (s&(1<<(i-1)) && s&(1<<(n+j-1)))
				{
					int res0=H[s][0],res1=H[s][1];
					H[s][0]=(res0*(1-a[i][j]+mod)%mod+res1*a[i][j]%mod)%mod;
					H[s][1]=(res0*a[i][j]%mod+res1*(1-a[i][j]+mod)%mod)%mod;
				}
	for (int s=0;s<(1<<V);s++)
	{
		Int res0=H[s][0],res1=H[s][1],sum=0;
		int u=s-(s&(-s));
		for (int t=u;t>0;t=(t-1)&u)
		{
			int val=Calc (s,t);
			if (val==0) continue;
			res0=res0-(Int) F[s^t][0]*H[t][0]*val;
			res0=res0-(Int) F[s^t][1]*H[t][1]*val;
			res1=res1-(Int) F[s^t][0]*H[t][1]*val;
			res1=res1-(Int) F[s^t][1]*H[t][0]*val;
			sum=sum+(Int) G[t]*F[s^t][0]*val;
			sum=sum+(Int) (G[t]+1)*F[s^t][1]*val;
		}
		F[s][0]=(res0%mod+mod)%mod;
		F[s][1]=(res1%mod+mod)%mod;
		sum+=F[s][1];
		G[s]=sum%mod;
	}
	printf ("%lld\n",G[(1<<V)-1]);
}

signed main ()
{
	T=read ();
	while (T--)
	{
		Init ();
		Work ();
	}
	return 0;
}